分数: 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