AtCoder ABC #145 : E - All-you-can-eat

Fで方針ミスのタイムロスしたのが痛い。
https://atcoder.jp/contests/abc145/tasks/abc145_e

問題

N個の料理があり、それぞれ食べるのにかかる時間と、おいしさが設定されている。
料理の食べる順は任意だが、1個食べ終わらないと次は食べられない。
時間T以内に食べ始めた料理は、時間Tを超えても最後まで食べられるとする。

最適な順で料理を食べたとき、得られるおいしさの総和はいくつか。

解法

最後にi番の料理を食べるとする。
[0,i-1]番の料理と[i+1,N-1]番の料理のうち、時間(T-1)以下で食べきれる料理のおいしさの総和の最大値がわかれば、それにi番の料理のおいしさを足したものが解の候補になる。

これがわかると、料理群のPrefixとSuffixについて総時間に対するおいしさの総和の最大値を求めるDPを行っておけばよいことがわかる。

int N,T;
int A[3030],B[3030];
int L[3030][3030];
int R[3030][3030];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		FOR(x,3030) {
			L[i+1][x]=max(L[i+1][x],L[i][x]);
			if(x+A[i]<=T) L[i+1][x+A[i]]=max(L[i+1][x+A[i]],L[i][x]+B[i]);
		}
	}
	for(i=N-1;i>=0;i--) {
		FOR(x,3030) {
			R[i][x]=max(R[i][x],R[i+1][x]);
			if(x+A[i]<=T) R[i][x+A[i]]=max(R[i][x+A[i]],R[i+1][x]+B[i]);
		}
	}
	FOR(i,N+1) {
		FOR(j,T) {
			L[i][j+1]=max(L[i][j],L[i][j+1]);
			R[i][j+1]=max(R[i][j],R[i][j+1]);
		}
	}
	
	
	int ma=0;
	FOR(i,N) {
		FOR(x,T) {
			y=B[i]+L[i][x]+R[i+1][T-1-x];
			ma=max(ma,y);
		}
	}
	cout<<ma<<endl;
}

まとめ

Editorial見るともっとシンプルに解く方法もあるようね。