← 返回题目列表

AtCoder · awc0014_a

A. 装载货物

中文机器翻译题面 查看原题

分数: 200 分

问题陈述

高桥在一家航运公司工作。今天,他负责将货物装载到 N 卡车。

要装载到卡车上的物品 i (1 \leq i \leq N) 都具有相同的重量 P_i 每公斤。高桥将这些物品一一装入。

每辆卡车的共同重量为 T 公斤。加载时 k 物品装上卡车 i,物品总重量不得超过 T 公斤。也就是说, P_i \times k \leq T 必须保留。

此外,还有一个共同的上限 R 每辆卡车上可装载的物品数量。即使未达到承重能力,该卡车的装载也会结束一次 R 项目已加载。

对于每辆卡车 i,确定最大项目数 r_i 可以在满足重量容量和物品数量限制的情况下装载。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq R \leq 10^9
  • 1 \leq T \leq 10^{18}
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

N R T
P_1 P_2 \ldots P_N
  • 第一行包含一个整数 N 代表卡车数量,整数 R 代表每辆卡车可以装载的物品数量上限,一个整数 T 代表承重能力,以空格分隔。
  • 第二行包含整数 P_1, P_2, \ldots, P_N 表示每辆卡车装载的一件物品的重量,以空格分隔。

输出

输出 N 整数 r_1, r_2, \ldots, r_N 在一行上用空格分隔,其中 r_i 是卡车上可以装载的最大物品数量 i.


示例输入 1

3 5 20
3 5 7

示例输出 1

5 4 2

示例输入 2

4 10 15
1 4 8 16

示例输出 2

10 3 1 0

示例输入 3

10 100 1000
1 2 5 10 50 100 200 333 500 1001

示例输出 3

100 100 100 100 20 10 5 3 2 0

示例输入 4

20 1000000000 1000000000000000000
1 2 3 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 999999999 500000000 250000000 123456789 777777777 42 314159265 271828182

示例输出 4

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

示例输入 5

1 1000000000 1
1000000000

示例输出 5

0