Submission #500836

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b) FOR(i,0,b)
#define PB push_back
#define BE(c) c.begin(),c.end()
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef long double ld;
typedef int ut;
typedef pair<ut,ut> pr;
typedef vector<ut> VI;
typedef vector<pr> Vpr;
const ut INF=1<<30;
const LL p=7+1e+9;
const int SIZE=1+2*1e+3;
using namespace std;
Vpr changes;
VI user;
int N,K;
int sums[SIZE][SIZE];
int maps[SIZE][SIZE];
int numbering(int sx,int sy,int ex,int ey){
	if(sx==0 || sy==0 || ex==N+1 || ey==N+1) return 0;
	return abs(sums[ey][ex]-sums[ey][sx-1]-sums[sy-1][ex]+sums[sy-1][sx-1]);
}
int solve(){
	int sx=INF,sy=INF,ex=0,ey=0;
	REP(i,user.size()){
		sx=min(sx,changes[user[i]].S);
		sy=min(sy,changes[user[i]].F);
		ex=max(ex,changes[user[i]].S);
		ey=max(ey,changes[user[i]].F);
	}
	int maxim=0;
	REP(j,2)
		REP(k,2)	
			REP(l,2)
				REP(v,2) 
					maxim=max(maxim,numbering(sx-j,sy-k,ex+l,ey+v));
	return maxim; 
}
int main() {
	int y,x;
	cin >> N >> K;
	
	FOR(i,1,N+1)
		FOR(j,1,N+1){
			maps[i][j]=((i+j)&1)?1:-1;	
		}	
	REP(i,K){
		cin >> y >> x;
		maps[y][x]*=-1;
		changes.PB(pr(y,x));
	}
	FOR(i,1,N+1)
		FOR(j,1,N+1)
			sums[i][j]=sums[i][j-1]+sums[i-1][j]-sums[i-1][j-1]+maps[i][j];
	int maxim=0;
	FOR(i,1,1<<K){
		REP(j,K) if(i&(1<<j)) user.PB(j);
		maxim=max(solve(),maxim);
		user.clear();
	}
	cout << maxim << endl;
	return 0;
}

Submission Info

Judge Result