D. R2D2 and Droid Army
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
An army ofndroids is lined up in one row. Each droid is described bymintegersa1,a2,…,am, whereaiis the number of details of thei-th type in this droid’s mechanism. R2-D2 wants to destroy the sequence of consecutive droids of maximum length. He hasmweapons, thei-th weapon can affect all the droids in the army by destroying one detail of thei-th type (if the droid doesn’t have details of this type, nothing happens to it).
A droid is considered to be destroyed when all of its details are destroyed. R2-D2 can make at mostkshots. How many shots from the weapon of what type should R2-D2 make to destroy the sequence of consecutive droids of maximum length?
Input
The first line contains three integersn,m,k(1≤n≤105,1≤m≤5,0≤k≤109) — the number of droids, the number of detail types and the number of available shots, respectively.
Nextnlines follow describing the droids. Each line containsmintegersa1,a2,…,am(0≤ai≤108), whereaiis the number of details of thei-th type for the respective robot.
Output
Printmspace-separated integers, where thei-th number is the number of shots from the weapon of thei-th type that the robot should make to destroy the subsequence of consecutive droids of the maximum length.
If there are multiple optimal solutions, print any of them.
It is not necessary to make exactlykshots, the number of shots can be less.
Sample test(s)
input
5 2 44 01 22 10 21 3
output
2 2
input
3 2 41 21 32 2
output
1 3
Note
In the first test the second, third and fourth droids will be destroyed.
In the second test the first and second droids will be destroyed.
线段树维护一个二分出答案
#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<iostream>#include<algorithm>#include<bitset>#include<climits>#include<list>#include<iomanip>#include<stack>#include<set>using namespace std;struct node{int l,r,mx[5];}tree[int(4e5)];int n,m,k;void build(int l,int r,int index){tree[index].l=l;tree[index].r=r;if(l==r){for(int i=0;i<m;i++)scanf("%d",tree[index].mx+i);return;}int mid=(l+r)>>1;build(l,mid,index<<1);build(mid+1,r,index<<1|1);int lson=index<<1,rson=index<<1|1;for(int i=0;i<m;i++)tree[index].mx[i]=max(tree[lson].mx[i],tree[rson].mx[i]);}int tmx[5];void seek(int l,int r,int index){if(l==tree[index].l&&r==tree[index].r){for(int i=0;i<m;i++)tmx[i]=max(tmx[i],tree[index].mx[i]);return;}int mid=(tree[index].l+tree[index].r)>>1;if(r<=mid)seek(l,r,index<<1);else if(l>mid)seek(l,r,index<<1|1);else{seek(l,mid,index<<1);seek(mid+1,r,index<<1|1);}}int knum,snum,ans[5];void work(){int l=1,r=n;while(l<=r){bool flag=0;int mid=(l+r)>>1;for(int i=1;i+mid-1<=n;i++){memset(tmx,0,sizeof(tmx));seek(i,i+mid-1,1);int sum=0;for(int i=0;i<m;i++)sum+=tmx[i];if(sum<=k){flag=1;if(knum<mid||(knum==mid&&snum>sum)){knum=mid;snum=sum;for(int i=0;i<m;i++)ans[i]=tmx[i];}}}if(flag)l=mid+1;elser=mid-1;}}int main(){cin>>n>>m>>k;build(1,n,1);work();cout<<ans[0];for(int i=1;i<m;i++)cout<<" "<<ans[i];}
，快乐要懂得分享，才能加倍的快乐
