当前位置: 代码迷 >> 综合 >> 【CodeForces - 514D 】R2D2 and Droid Army(尺取法)
  详细解决方案

【CodeForces - 514D 】R2D2 and Droid Army(尺取法)

热度:36   发布时间:2023-12-06 19:33:23.0

有 n 个机器人站成一排。每个机器人可以表示成 m 个整数 a1,?a2,?...,?am,其中 ai 是机器人的第 i 项特征值。 R2-D2 想要摧毁尽量多的连续的机器人。 他有 m 种武器, 第 i 种武器可以将所有机器人第 i 项特征值减少1。 (如果该机器人的特征值已经为0,则什么都不发生).

如果一个机器人所有特征值都为0,则认为该机器人被摧毁。R2-D2 可以用 k 次武器。问 R2-D2 最多可以摧毁多少连续的机器人?

Input

第一行包含三个整数 n,?m,?k (1?≤?n?≤?105, 1?≤?m?≤?5, 0?≤?k?≤?109) — 分别表示机器人数,特征值数和可以动用武器的次数。

之后 n 行每行描述一个机器人。每行包含 m 个整数 a1,?a2,?...,?am (0?≤?ai?≤?108),其中 ai是这个机器人的第 i 项特征值。

Output

输出 m 个用空格分开的数,其中第 i 个数表示第 i 种武器使用的次数。

如果有多种方案,输出任意一种。

可以使用少于 k 次射击。

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

第一个样例中,第2、3、4个机器人被摧毁了。

第二个样例中,第2、3个机器人被摧毁了。

思路:

尺取,每次都维护5个值,同时每次都尝试更新最优解。用multiset维护已经选的元素,set中第一个为最大值。

ac代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#include<unordered_map>
#define mod (1000000007)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+10;
int n,m,k;
int a[maxn][5];
multiset<int,greater<int>> st[5];
int ans[5],res=0;
int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=0;j<m;j++)scanf("%d",&a[i][j]);	for(int l=1,r=1;r<=n;){while(r<=n){int sum=0;for(int i=0;i<m;i++)st[i].insert(a[r][i]),sum+=*(st[i].begin());r++;if(st[0].size()>res&&sum<=k){//每次都更新最优解,用0号属性来判断,因为别的属性可能没有 res=st[0].size();for(int i=0;i<m;i++)ans[i]=*(st[i].begin());}if(sum>k) break;}for(int i=0;i<m;i++)st[i].erase(a[l][i]);l++;}for(int i=0;i<m;i++)printf("%d%c",ans[i],i==m?'\n':' ');return 0;
}