Submission #502294

---

Source Code Expand

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

#define rep2(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) rep2(i,0,n)
#define inf (1e9)
#define eps (1e-9)
int d[2000][2000];

long long check(int i, int j, int s, int t, int n) {
    if (i < 0 || j < 0) return 0;
    if (s >= n || t >= n) return 0;
    long long red = 0, blue = 0;
    for (int x = i; x <= s; x++) {
      for (int y =j; y <= t; y++) {
	if (d[x][y] == 0) {
	  red++;
	} else {
	  blue++;
	}
      }
    }
    return abs(red-blue);  
}

int main() {
  int N,K; cin >> N >> K;
  vector<pair<int,int> > k;
  for (int i =0; i< N; i++) {
    for (int j=0; j < N; j++) {
      if ((i+j) % 2 == 0) {
	d[i][j] = 1;
      } else {
	d[i][j] = 0;
      }
    }
  }
  for (int i = 0; i < K; i++) {
    int x,y;
    cin >> x >> y;
    x--; y--;
    k.push_back(make_pair(x,y));
    if (d[x][y] == 0) {
      d[x][y] = 1;
    } else {
      d[x][y] = 0;
    }
  }

  long long res = 0;
  for (int i = 0; i < (1 << k.size()); i++) {
    int min_i = N-1, min_j = N-1, max_i = 0, max_j = 0;
    for (int j = 0; j < k.size(); j++) {
      if (i >> j & 1) {
	max_i = max(k[j].first, max_i);
	max_j = max(k[j].second, max_j);
	min_i = min(k[j].first, min_i);
	min_j = min(k[j].second, min_j);
      }
    }
    //cout << min_i << " " << min_j << endl;
    //cout << max_i << " " << max_j << endl;
    int g[3] = {-1,0,1};
    rep(a,3) {
      rep(b,3) {
        rep(c,3) {
	  rep(d,3) {
            res = max(res,check(min_i+g[a],min_j+g[b],max_i+g[c],max_j+g[d],N));
	  }
	}
      }
    }
  }
  
  cout << res << endl;
  return 0;
}

Submission Info

Judge Result