問題文の解読が難しい。
http://codeforces.com/contest/514/problem/D
問題
N個のドローンがある。
各ドローンにはM種類の構成部品があり、i番のドローンにはj番目の部品がA[i][j]個使われている。
ここでM種類の武器がある。
j番の武器を1回放つと、各ドローンのj番目の部品が1個ずつ破壊される。
全構成部品を破壊したドローンは破壊される。
武器を全部でK回使い、出来るだけ連続したドローンを破壊したい。
連続したドローン破壊数が最大となる、各武器の発射回数を求めよ。
解法
L~R番のドローンを破壊するには、であればよい。
後は各Lについて上記条件を満たす最大のRを求めればよい。
この手段はいくつかあって、
- 尺取法でRを検索していく
- A[i][j]のSegTreeを作るとが簡単に求められるので二分探索でRを求める
- 平方分割で一定区間のを求めていくことで、RをO(√N)で求める。
自分は最後の平方分割解だったけど、SegTree解が一番スマートかな?
速度は尺取法が一番速そうだね。
int N,M,K; int D=400; ll A[101000][7]; ll MM[400][7]; int co=0; int res[7]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>K; FOR(i,N) FOR(j,M) cin>>A[i][j], MM[i/D][j]=max(MM[i/D][j],A[i][j]); FOR(i,N) { ll ma[6]={}; if(N-i<=co) continue; for(x=i;x<N;) { ll tma[6]; ll tot=0; if(x%D==0 && x+D<N) { FOR(j,M) tot+=tma[j]=max(MM[x/D][j],ma[j]); if(tot<=K) { x+=D; FOR(j,M) ma[j]=tma[j]; continue; } } tot=0; FOR(j,M) tot+=tma[j]=max(A[x][j],ma[j]); if(tot>K) break; FOR(j,M) ma[j]=tma[j]; x++; } if(x-i>co) { co=x-i; FOR(j,M) res[j]=ma[j]; } } FOR(j,M) _P("%d ",res[j]); _P("\n"); }
まとめ
まさかの平方分割2連発。