R2D2 and Droid Army
An army of n droids is lined up in one row. Each droid is described by m integers a1, a2, …, am, where ai is the number of details of the i-th type in this droid’s mechanism. R2-D2 wants to destroy the sequence of consecutive droids of maximum length. He has m weapons, the i-th weapon can affect all the droids in the army by destroying one detail of the i-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 most k shots. 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 integers n, 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.
Next n lines follow describing the droids. Each line contains m integers a1, a2, …, am (0 ≤ ai ≤ 108), where ai is the number of details of the i-th type for the respective robot.
Output
Print m space-separated integers, where the i-th number is the number of shots from the weapon of the i-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 exactly k shots, the number of shots can be less.
Example
Input
5 2 4
4 0
1 2
2 1
0 2
1 3
Output
2 2
Input
3 2 4
1 2
1 3
2 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.
题意：有n个机器人，每个机器人有m个描述，你有k次机会，每次都可以选择m中的一个，让n个机器人的这个描述减1，当某个机器人的m个描述都减为0了，这个机器人就没了，问的是用这k次机会可以消灭最多 多少连续的机器人，最后把每个描述用的机会输出来。注意：就是所有m个描述所用机会的总和不一定要等于k次，也可以小于。
题意：二分长度len，枚举n行是否存在这样的i~i+len-1，所需要的子弹数<=k，存在则表示len可行,然后我们可以先预处理出对于第x个描述，在区间（l,r）之间最大的描述值，预处理可以用RMQ处理
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+10;
int dp[6][maxn][20];//dp[i][j][k]表示第i个描述中[j,j+2^(k)-1]的最大值
int a[maxn][10];//a[i][j]表示第i个机器人的第j个描述
int n,m,k;
void RMQ_init(int n,int m){//预处理
for (int i=1;i<=m;i++){
for (int j=1;j<=n;j++){
dp[i][j][0]=a[j][i];
}
}
for (int i=1;i<=m;i++)
for (int k=1;(1<<k)<=n;k++){
for (int j=1;j+(1<<k)-1<=n;j++){
dp[i][j][k]=max(dp[i][j][k-1],dp[i][j+(1<<(k-1))][k-1]);
}
}
}
int RMQ(int l,int r,int cnt){//查找第cnt个描述中[l,r]之间的最大值
int k=0;
//k=(int)log(r-l+1)/log(2.0);
while((1<<(k+1))<=r-l+1)k++;
return max(dp[cnt][l][k],dp[cnt][r-(1<<k)+1][k]);
}
int f(int x){//判断是否有x个连续的机器人给消灭，如果可以返回第一个机器人的位置
for(int i=1;i+x-1<=n;i++){
ll sum=0;
for (int j=1;j<=m;j++){
sum+=(RMQ(i,i+x-1,j));
}
if (sum<=k)return i;
}
return 0;
}
int main()
{
while (scanf ("%d%d%d",&n,&m,&k)!=EOF){
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
scanf ("%d",&a[i][j]);
}
}
RMQ_init(n,m);//预处理
int lo=0,hi=n;
int mid;
int ans=0;
int place=0;//标记从第几个机器人开始的连续ans个机器人
while (lo<=hi){
int mid=(hi+lo)/2;
int tmp=f(mid);
if (tmp){//如果可以
lo=mid+1;
if (ans<=mid){//记录最大 的值
ans=mid;
place=tmp;
}
}
else hi=mid-1;
}
// printf ("%d %d\n",ans,place);
for (int i=1;i<=m;i++){//输出
if (i==1)printf ("%d",RMQ(place,place+ans-1,i));
else printf (" %d",RMQ(place,place+ans-1,i));
}
printf ("\n");
}
return 0;
}