[BOJ 17779] 게리맨더링 2

백준 :: BOJ :: 17779 :: 게리맨더링 2

 

출처 : https://www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

#include <bits/stdc++.h>
using namespace std;

#define F(p,q,r) for(int p=q; p<r; p++)
int N, A[20][20], s, t, ans = 1e5, v, D[4][2] = { {0,-1},{1,0},{0,1},{-1,0} };

int main() {
	cin >> N;
	F(i, 0, N) {
		F(j, 0, N) {
			cin >> A[i][j]; s += A[i][j];
		}
	}
	F(i, 0, N - 2) {
		F(j, 1, N - 1) {
			F(n1, 1, j + 1) {
				F(n2, 1, N-j) {
					if (i + n1 + n2 >= N) break;
					t = s; int B[5] = { 0, }, ma = 0, mi = 1e5,
						C[4][6] = { {0,i+n1,i,0,j+1,N},{0,i+n2+1,i+1,j+1,N,N},
					{i+n1,N,0,0,j-n1-1,i+n1+n2+1},{i+n2+1,N,0,j+n2+1,N,i+n1+n2+2} };
					F(k, 0, 4) {
						v = 0; F(y, C[k][0], C[k][1]) {
							if (y >= C[k][2] && y<C[k][5]) v++;
							int c1 = C[k][3] + D[k][0]*v, c2= C[k][4] + D[k][1]*v;
							F(x, c1, c2) B[k] += A[y][x];
						}
						ma = max(ma, B[k]); mi = min(mi, B[k]); t -= B[k];
					} ma = max(ma, t); mi = min(mi, t);
					ans = min(ans, ma-mi);
				}
			}
		}
	}
	cout << ans;
	return 0;
}