Codeforces #691 Div1 B. Glass Half Spilled

ここまでは良かったんだが。
https://codeforces.com/contest/1458/problem/B

問題

N個のグラスがあり、それぞれ最大容量A[i]と今水が入っている容量B[i]が与えられる。
水の入ったグラスから、任意回数他のグラスに水を移すことができる。
ただしその時、元のグラスから水がx減った場合に、移した先にはx/2しか水が追加されない（残りはこぼれてしまう）。

任意に選んだk個のグラスに水を集めるとき、水の総量を最大化したい。
k=1～Nのそれぞれについて、その総量を答えよ。

解法

極力水は動かさない方が良い。
そこで以下を求めよう。
dp(n,c) := n個のグラスに水を集める場合、グラスの総容量がcであるように選んだ場合の、元々ある水の総容量

もし水の総量がSの時、kを定めたときの解はmax(min(c,dp(n,c)+(S-dp(n,c)/2)となる。
dp(n,c)はO(N^2*sum(A))で埋められる。

int dp[101][10101];
int N,S;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,101) FOR(x,10100) dp[i][x]=-1<<30;
	dp[0][0]=0;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		S+=y;
		for(j=i;j>=0;j--) FOR(k,j*100+1) dp[j+1][k+x]=max(dp[j+1][k+x],dp[j][k]+y);
	}
	
	for(i=1;i<=N;i++) {
		double ma=0;
		FOR(j,10100) if(dp[i][j]>=0) {
			ma=max(ma,min((double)j,dp[i][j]+(S-dp[i][j])/2.0));
		}
		_P("%.12lf ",ma);
	}
	
}

まとめ

ここまで15分だったのに…。