なかなか時間通りに参加することが難しいですね。
https://yukicoder.me/problems/no/710
問題
N個の問題を2人で解くことを考える。
1つの問題はいずれか1人しか解くことができない。
また、1人は同時に1つの問題しか解けない。
i問目を解く時間がそれぞれA[i]、B[i]かかる場合、最適な配分をしたときに全問解き終わる最短時間を求めよ。
解法
以下を考える。
f(i,x) := i問目までのうち何問かを1人目が解いた場合の合計時間がxである場合、残りを2人目が解いたときの最短時間
これをメモ化再帰なりDPなりで埋めていけばよい。
最終的にmax(f(N,x),x)の最小値が解。
状態としてはO(N^2*max(A,B))程度なので、何とか間に合う。
int N; int A[101],B[101]; int from[101010]; int to[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,101000) from[i]=1<<30; from[0]=0; FOR(i,N) { cin>>A[i]>>B[i]; FOR(j,101000) to[j]=1<<30; FOR(j,100001) { to[j+A[i]]=min(to[j+A[i]],from[j]); to[j]=min(to[j],from[j]+B[i]); } swap(from,to); } int mi=1<<30; FOR(i,101000) mi=min(mi,max(i,from[i])); cout<<mi<<endl; }
まとめ
No.709の方が難しいかも?