TopCoder SRM 636 Div1 Easy ChocolateDividingEasy

SRM636に参加。
Easy早解き逃げ切りでレート上昇という、久々に自分らしいスタイルだった。
Mediumはsubmitにすら至らなかったのが残念。
http://community.topcoder.com/stat?c=problem_statement&pm=13497

問題

N*Mのグリッド状のチョコレートがあり、それぞれのセルは0-9のおいしさである。
このチョコレートに対し、縦に2本、横に2本切込みを入れて9個に分割したとき、分割した各領域のおいしさの和のうち、最小のものが自分のものになる。

最適な切込みを入れることで、自分が得られる領域のおいしさの総和の最大値を求めよ。

解法

事前にO(HW)かけて2次元の累積和を取っておけば、各領域のおいしさの総和をO(1)でとれるようになる。
後は分割位置を総当たりするだけ。
よってO(H^2*W*2)で回答可能。

int S[60][60];
class ChocolateDividingEasy {
	public:
	int sum(int x1,int y1,int x2,int y2) {
		return S[y2][x2]-S[y1][x2]-S[y2][x1]+S[y1][x1];
	}
	
	int findBest(vector <string> C) {
		int H=C.size(), W=C[0].size();
		int x,y,mi=0;
		ZERO(S);
		FOR(y,H) {
			FOR(x,W) S[y+1][x+1]=S[y+1][x]+C[y][x]-'0';
			FOR(x,W) S[y+1][x+1]+=S[y][x+1];
		}
		int x1,x2,y1,y2;
		for(y1=1;y1<=H;y1++) for(y2=y1+1;y2<=H;y2++) {
			for(x1=1;x1<W;x1++) for(x2=x1+1;x2<=W;x2++) {
				int v=99999999;
				v=min(v,sum(0,0,x1,y1));
				v=min(v,sum(x1,0,x2,y1));
				v=min(v,sum(x2,0,W,y1));
				v=min(v,sum(0,y1,x1,y2));
				v=min(v,sum(x1,y1,x2,y2));
				v=min(v,sum(x2,y1,W,y2));
				v=min(v,sum(0,y2,x1,H));
				v=min(v,sum(x1,y2,x2,H));
				v=min(v,sum(x2,y2,W,H));
				mi=max(mi,v);
			}
		}
		return mi;
	}
}

まとめ

久々にえらい安直なEasyが出たな。