Codeforces #419 Div1 A. Karen and Game

うーん、しょうもないミス。
http://codeforces.com/contest/815/problem/A

問題

N行M列の行列Aが与えられる。
全要素ゼロの行列から始め、列または行の要素をインクリメントすることを繰り返し、Aを構築できるか。
できるならインクリメント回数が最小のものの一例を答えよ。

解法

1箇所、例えば先頭行のインクリメント数を総当たりすれば、先頭行を見ることで各列のインクリメント数が決まり、先頭列から各行のインクリメント数が決まる。
あとはそれらのインクリメント回数とAが矛盾しないか判定しよう。

int H,W;
int G[505][505];
int R[505],C[505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>G[y][x];
	vector<pair<int,int>> cand;
	for(R[0]=0;R[0]<=500;R[0]++) {
		FOR(x,W) C[x]=G[0][x]-R[0];
		for(y=1;y<H;y++) R[y]=G[y][0]-C[0];
		int ok=1;
		FOR(y,H) FOR(x,W) {
			if(R[y]<0 || C[x]<0) ok=0;
			if(R[y]+C[x]!=G[y][x]) ok=0;
		}
		if(ok==0) continue;
		int tot=0;
		FOR(y,H) tot+=R[y];
		FOR(x,W) tot+=C[x];
		cand.push_back({tot,R[0]});
	}
	
	sort(ALL(cand));
	if(cand.size()) {
		R[0]=cand[0].second;
		FOR(x,W) C[x]=G[0][x]-R[0];
		for(y=1;y<H;y++) R[y]=G[y][0]-C[0];
		_P("%d\n",cand[0].first);
		FOR(y,H) FOR(i,R[y]) _P("row %d\n",y+1);
		FOR(x,W) FOR(i,C[x]) _P("col %d\n",x+1);
	}
	else {
		_P("-1\n");
	}
	
}

まとめ

最小を見落としたせいでレート減。