cf514d+rmq+二分

给定n个物体，每个物体有M个属性，每次射击可以减少物体属性（0就死了），最多可以射击k次，问最多连续射死多少个？

直接二分最大的长度，再用RMQ查询

using namespace std;
typedef long long LL;
const int Maxn=1e5+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int a[10][Maxn],dp[10][Maxn][20],ans[Maxn];
int n,m,k;
void ()
{
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
			dp[i][j][0]=a[i][j];
		for(int l=1;(1<<l)<=n;l++)
			for(int j=1;(j+(1<<l)-1)<=n;j++)
				dp[i][j][l]=max(dp[i][j][l-1],dp[i][j+(1<<(l-1))][l-1]);
	}
}
int query(int i,int l,int r){
	int k=0;
	while((1<<(k+1))<=r-l+1) k++;
	return max(dp[i][l][k],dp[i][r-(1<<k)+1][k]);
}
bool check(int mid)
{
	for(int i=1;i+mid-1<=n;i++)
	{
		int need=0;
		for(int j=1;j<=m;j++)
			need+=query(j,i,i+mid-1);
		if(need<=k){
			ans[mid]=i;
			return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[j][i]);
	RMQ();
	int L=0,R=n+1,mid=1;
	while(R-L>1){
		mid=(L+R)>>1;
		if(check(mid)) L=mid;
		else R=mid;
	}
	for(int i=1;i<=m;i++)
		printf("%d ",query(i,ans[L],ans[L]+L-1));
	return 0;
}