Codeforces #264 Div2 C. Gargari and Bishops

CF#264に参加。
せっかく全完チャンスなのにこのCでポカミスした。
まぁEが解けたおかげで悪くない順位。
http://codeforces.com/contest/463/problem/C

問題

NxNのグリッドがあり、各セルにポイントが割り振られている。
このグリッドに、斜め方向に何マスでも移動できる２個のビショップを置きたい。
ただし、２個のビショップ両方から到達可能なセルがあるような配置はできない。

２つのビショップを置くと、それぞれ１手で移動可能な範囲内のセルのポイントの合計が得られる。
最大ポイント数を得られるビショップの置き方を答えよ。

解法

２つのビショップの座標の(x+y)%2が一致すると、両方のビショップから到達可能なセルができてしまう。
よって、(x+y)の偶奇それぞれで１個ずつビショップを置くことを考える。
後は互いのビショップがぶつかることを考えなくていいので、各セルにビショップを置いた際に得られるポイント計算し、それぞれ最大値を求めればよい。

事前に斜め方向のセルの累積和を取っておくと、各セルにビショップを置いた際のポイントはO(1)で得られるので全体でO(N^2)。

int N;
ll A[2010][2010];
ll L[5000],R[5000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	int xx[2],yy[2];
	cin>>N;
	FOR(y,N) FOR(x,N) {
		cin>>A[y][x];
		L[y+x]+=A[y][x];
		R[2500+y-x]+=A[y][x];
	}
	ll h[2]={-1,-1};
	FOR(y,N) FOR(x,N) {
		i=(x+y)%2;
		ll ho=L[y+x]+R[2500+y-x]-A[y][x];
		if(ho>h[i]) {
			h[i]=ho;
			xx[i]=x+1;
			yy[i]=y+1;
		}
	}
	_P("%I64d\n%d %d %d %d\n",h[0]+h[1],yy[0],xx[0],yy[1],xx[1]);
}

まとめ

答えに0ポイントがあり得るので、最大値を求めるとき初期値を0にするとミスする。
…実際自分がそれをやって落とした。