Codeforces #408 (Div. 2) E: Exam Cheating
dp[i][j][fs][sc]
=i番目まの問題まで確定していて、j回カンニングしている。１人目に対して直前にしたカンニングの左端はiからfs個左、2人目に対して直前にしたカンニングの左端はiからsc個左とする。ただし、fs,scはK以上はすべてKの1値で表す。このとき最大の得点。
この愚直なDPの計算量は
O(n*p*k^2)
n*p*k^2≦1000*1000*50^2 = 2.5*10^9
で間に合わない。
もっと容易に解が求まる場合を考えてみる。
2人対してすべての問題をカンニングできる場合を考える。
この場合は
p≧2*ceil(n/k)
と同値。このとき得点しうる問題はすべて得点できる。
そうでない場合は
p<2*ceil(n/k)
が成り立つ。
このとき
O(n*p*k^2)
= O(n*(n/k)*k^2)
= O(n^2 * k)
となり、間に合う。
