← 返回题目

题库练习 R2D2 and Droid Army

← 上一题下一题 →

A6895 | $R2D2 and Droid Army$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有一队 $n$ 个机器人排成一行。每个机器人由 $m$ 个整数 $a_{1},a_{2},...,a_{m}$ 描述，其中 $a_{i}$ 表示该机器人机械中第 $i$ 类部件的数量。R2-D2 想要摧毁一段尽可能长的连续机器人序列。他有 $m$ 种武器，第 $i$ 种武器能够通过摧毁 $i$ 类部件，对整个队列所有机器人产生影响（如果机器人没有该类部件，则无影响）。 当一个机器人的所有部件都被摧毁时，该机器人被认为已被摧毁。R2-D2 最多可以进行 $k$ 次射击。为了摧毁一段最长的连续机器人物列，他应该对每种武器分别射击多少次？

输入格式

第一行为三个整数 $n,m,k$（$1 \leq n \leq 10^{5}$，$1 \leq m \leq 5$，$0 \leq k \leq 10^{9}$），分别表示机器人的数量、部件类型的数量和可用射击次数。 接下来的 $n$ 行每行包含 $m$ 个整数 $a_{1},a_{2},...,a_{m}$（$0 \leq a_{i} \leq 10^{8}$），其中 $a_{i}$ 表示对应机器人的第 $i$ 类部件的数量。

输出格式

输出 $m$ 个用空格分隔的整数，第 $i$ 个数表示应对第 $i$ 种武器射击的次数，以摧毁一段最长的连续机器人序列。 如果有多组最优解，输出任意一组均可。 不要求恰好射击 $k$ 次，射击次数可以更少。

输入输出样例

输入 #1

输出 #1

2 2

输入 #2

输出 #2

1 3

C++ 编辑器

输入

输出