16971번 배열 B의 값

parkit 2019. 4. 21. 14:03
728x90
https://www.acmicpc.net/problem/16971
좋은 문제같다.
나중에 다시 풀어볼 문제이다.
복습!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int N = 0, M = 0;
int A[1010][1010] = { 0, }, r[1010] = { 0, }, c[1010] = { 0, };
 
void row_change(int r1, int r2)
{
    for (int j = 0; j < M; j++)
        swap(A[r1][j], A[r2][j]);
}
 
void column_change(int c1, int c2)
{
    for (int i = 0; i < N; i++)
        swap(A[i][c1], A[i][c2]);
}
 
int B()
{
    int ret = 0;
 
    for (int i = 0; i < N - 1; i++)
        for (int j = 0; j < M - 1; j++)
            ret += A[i][j] + A[i + 1][j] + A[i + 1][j + 1] + A[i][j + 1];
 
    return ret;
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            scanf("%d", &A[i][j]);
 
    for(int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            r[i] += A[i][j];
            c[j] += A[i][j];
        }
 
    int MAX = B(), rmin = 987654321, rmin_idx = -1, cmin = 987654321, cmin_idx = -1;
 
    for (int i = 1; i < N - 1; i++) // 0과 N - 1은 교환해야하므로, 제외한다.
    {    
        r[i] *= 4;
 
        r[i] -= 2 * (A[i][0] + A[i][M - 1]); // N, M 구별 주의
 
        if (rmin > r[i])
        {
            rmin = r[i];
            rmin_idx = i;
        }
    }
 
    for (int j = 1; j < M - 1; j++) // 0과 M - 1은 교환해야하므로, 제외한다.
    {
        c[j] *= 4;
 
        c[j] -= 2 * (A[0][j] + A[N - 1][j]); // N, M 구별 주의
 
        if (cmin > c[j])
        {
            cmin = c[j];
            cmin_idx = j;
        }
    }
 
    if (rmin_idx != -1)
    {
        row_change(0, rmin_idx);
        MAX = max(MAX, B());
        row_change(0, rmin_idx);
 
        row_change(N - 1, rmin_idx);
        MAX = max(MAX, B());
        row_change(N - 1, rmin_idx);
    }
 
    if (cmin_idx != -1)
    {
        column_change(0, cmin_idx);
        MAX = max(MAX, B());
        column_change(0, cmin_idx);
 
        column_change(M - 1, cmin_idx);
        MAX = max(MAX, B());
        // 끝까지 와서는 굳이 바꿀 필요 없음.
    }
 
    printf("%d\n", MAX);
    
    return 0;
}
Colored by Color Scripter
cs
728x90
저작자표시 (새창열림)