TopCoder SRM 844 : Div1 Easy FeedADrake

2回でレート200以上落としてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=17801

問題

N個のケーキがあり、それぞれの大きさが与えられる。
いくつかのケーキを、任意の順で食べることを考える。
各ケーキは一度食べ始めたらすべて食べきらないといけない。

食べきれるケーキの総量は、お腹の容量Sと許容超過量Eで与えられる。
食べたケーキの総量がS以上になる最初のケーキまで食べきった後、追加であとE個ケーキを食べられる。
最適な順でケーキを食べた場合、食べられるケーキの総量はいくらか。

解法

総量S未満であれば任意にケーキを食べられ、あと(E+1)個ケーキを食べられると考えよう。
f(s,e) := お腹がいっぱいになる前に食べたケーキの総量がs、お腹がいっぱいになりながらorなった後に食べたケーキの個数がeの時の、食べたケーキの総量の最大値
として、DPでこのテーブルを埋めて行こう。
ケーキは、「食べない」「お腹いっぱいになる前に食べる」「お腹がいっぱいになりながらorなった後食べる」の3択となる。

ll dp[10101][105];

class FeedADrake {
	public:
	int feed(int stomach, vector <int> cakes, int excess) {
		
		int x,y;
		ZERO(dp);
		FORR(c,cakes) {
			
			for(x=stomach-1;x>=0;x--) {
				for(y=excess+1;y>=0;y--) {
					chmax(dp[x][y+1],dp[x][y]+c);
					if(x+c<stomach) chmax(dp[x+c][y],dp[x][y]+c);
				}
			}
		}
		ll ma=0;
		FOR(x,stomach) FOR(y,excess+2) ma=max(ma,dp[x][y]);
		return ma;
		
	}
}

まとめ

場合によってはお腹の容量の数万倍以上食べられる設定の問題。
ずいぶん無茶苦茶な食べ方ですね。