【CF簡介】

提交鏈接：CF 514D

題面：

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 of n droids is lined up in one row. Each droid is described bym integers a₁,?a₂,?...,?a_m, wherea_i is 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 hasm weapons, the i-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 mostk 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?≤?10⁵, 1?≤?m?≤?5, 0?≤?k?≤?10⁹) — 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 containsm integers a₁,?a₂,?...,?a_m (0?≤?a_i?≤?10⁸), where a_i is the number of details of thei-th type for the respective robot.

Output

Print m space-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 exactly k shots, the number of shots can be less.

Examples 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個(gè)有序排列的機(jī)器人，每個(gè)機(jī)器人有m項(xiàng)屬性，每個(gè)機(jī)器人的每項(xiàng)屬性并不統(tǒng)一。要消滅一個(gè)機(jī)器人，需要將他的每項(xiàng)屬性值都減為1，現(xiàn)在有k次操作機(jī)會(huì)，每次操作可以將每個(gè)機(jī)器人的某項(xiàng)屬性值都減1，問在不超過k次操作的情況下，如何分配每項(xiàng)屬性減幾次，可以使得最終消滅最多的連續(xù)機(jī)器人序列，輸出分配攻擊方案。

???? 注意：如果不能全部消滅，則每項(xiàng)輸出0，因?yàn)橐笙谋M量少的操作數(shù)，達(dá)到殺死盡量多連續(xù)的機(jī)器人。

解題：

???? RMQ，區(qū)間詢問問題，可以做到O（nlogn）復(fù)雜度預(yù)處理，O（log n）復(fù)雜度詢問，入門ST算法，可以看這篇博客，通過RMQ預(yù)處理好每項(xiàng)屬性，區(qū)間最大值。

???? 隨后詢問時(shí)，只要查詢出該區(qū)間每項(xiàng)屬性的最大值，隨后將這些最大值累加，即為消滅該區(qū)間全部機(jī)器人的最小操作次數(shù)。

???? 枚舉左端點(diǎn)，二分右區(qū)間，若區(qū)間需要操作數(shù)大于k，則左移右區(qū)間，縮小區(qū)間長度，若小于等于k則，右移右區(qū)間，增大區(qū)間長度。在二分過程中更新區(qū)間最優(yōu)值，同時(shí)還需記錄此時(shí)的分配情況，若區(qū)間長度相等的情況下，還需保證操作數(shù)盡量小。

代碼：

#include#include#include#include#include#include#include#include#define?LL?long?long
#define?maxn?100010
#define?sq(a)??1LL*(a)*(a)
#define?mod?1000000007
using?namespace?std;
int?arr[maxn][5],d[maxn][5][20],path[5],tmp[5];
int?n,m,k;
void?init()
{
??for(int?i=0;i<n;i++)
	??for(int?j=0;j<m;j++)
		??d[i][j][0]=arr[i][j];
??for(int?j=1;(1<<j)<=n;j++)
	??for(int?i=0;i+(1<<j)-1<n;i++)
		??for(int?k=0;k<m;k++)
			??d[i][k][j]=max(d[i][k][j-1],d[i+(1<<(j-1))][k][j-1]);
}
int?RMQ(int?le,int?ri)
{
	int?k=0,res=0;
	for(int?i=0;i<m;i++)
	{
		k=0;
		while((1<<(k+1))<=ri-le+1)
			k++;
		tmp[i]=max(d[le][i][k],d[ri-(1<<k)+1][i][k]);
		res+=tmp[i];
	}
	return?res;
}
void?update()
{				?
??for(int?j=0;j<m;j++)
	path[j]=tmp[j];
}
int?main()
{
	int?le,ri,temp,ans=0,ansk=0x3f3f3f3f;
	bool?flag=0;
	scanf("%d%d%d",&n,&m,&k);
????for(int?i=0;i<n;i++)
		for(int?j=0;j<m;j++)
			scanf("%d",&arr[i][j]);
	init();

	for(int?i=0;i<n;i++)
	{
??????le=i;
??????ri=n-1;
	??if(ri-le+1<ans)
		??break;
	??while(le>1;
		?temp=RMQ(i,mid);
		?if(tempans)
			?{
				?ansk=temp;
				?ans=mid-i+1;
				?update();
			?}
			?else?if(mid-i+1==ans)
			?{
				?if(ansk>temp)
				?{
					ansk=temp;
????????????????????update();
				?}
			?}
			?le=mid+1;
		?}
		?else
		?{
			?ri=mid-1;
			?if(ri-i+1<ans)
				?break;
		?}
	??}
	}
	printf("%d",path[0]);
	for(int?i=1;i<m;i++)
		printf("?%d",path[i]);
	printf("n");
	return?0;
}