Codeforces 514D

問題

N台のロボットが1列に並べてあり、各ロボットはM種類の精密機械で構成されている。
各精密機械は何個か積まれており、ロボットiのj番目の精密機械はk個(a[i][j]=k)という情報が与えられる。
今、特殊な兵器によって、1回につき、すべてのロボットについて、ある精密機械jをそれぞれ1個まで破壊することができる。
ロボットは精密機械がすべて壊されたとき、破壊される。
特殊な兵器は最大でも合計K回しか利用することができないとき、できるだけ長く連続したロボットを破壊したい。
そのような場合、各精密機械向けにそれぞれ何回使えばよいか答える。

N<=10^5
M<=5
K<=10^9
a[i][j]<=10^8

考え方

いろんな解法：http://d.hatena.ne.jp/phyllo_algo/20150216/1424102140

問題は、あるi〜jまでのロボットを破壊したいとき、そのロボットの各精密機械の最大個数の合計がK以下であれば、可能、というのを求めることになる。
ただし、愚直にi,jを定めて、その間のロボットの最大値を求めるとO(N^3*M)かかってしまうため無理。

i〜jが破壊可能である場合、i+1〜jやi〜j-1など部分集合も破壊可能であるので、計算を省略できる。
しゃくとり法(two pointers)を使って、s〜eが破壊可能である時、e+1のロボットを含めて条件を満たせばs〜e+1も破壊可能、条件を満たせなければ、始点を更新してs'〜e+1が破壊可能である最小のs'を見つけて更新していけばよい。
s'はe+1からs方向に向けて、条件を満たす間s'を更新し続けて探す方法でも間に合う。