Watering the Plants

题目描述

贝茜的花园里有 $N$ 株植物，从左到右编号为 $1$ 到 $N$（$2\leq N\leq 5\cdot 10^5$）。贝茜知道第 $i$ 株植物至少需要 $w_i$（$0\leq w_i \leq 10^6$）单位的水。

贝茜有一套非常奇特的灌溉系统，包含 $N-1$ 条水渠，编号为 $1$ 到 $N-1$。每条水渠 $i$ 有一个单位费用 $c_i$（$1\le c_i\le 10^6$），使得贝茜可以支付 $c_i k$，从而让植物 $i$ 和 $i+1$ 各获得 $k$ 单位的水，其中 $k$ 是非负整数。

贝茜很忙，可能没有时间使用所有水渠。对于每个 $2\leq i \leq N$，计算仅使用前 $i-1$ 条水渠时，给植物 $1$ 到 $i$ 浇足水所需的最小费用。

输入格式

第一行包含一个正整数 $N$。 第二行包含 $N$ 个用空格分隔的整数 $w_1, \ldots, w_N$。 第三行包含 $N-1$ 个用空格分隔的整数 $c_1, \ldots, c_{N-1}$。

输出格式

输出 $N-1$ 行整数。第 $(i-1)$ 行应为仅使用前 $i-1$ 条水渠时，给前 $i$ 株植物浇足水的最小费用。

3
39 69 33
30 29

2070
2127

3
33 82 36
19 1

1558
676

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49

623
4099
4114
6269
6272
6827
8827

提示

使用第一条水渠为前 $2$ 株植物浇足水的最小费用，是将第一条水渠使用 $69$ 次，支付 $30 \cdot 69 = 2070$。 为前 $3$ 株植物浇足水的最小费用，是将第一条水渠使用 $39$ 次、第二条水渠使用 $33$ 次，支付 $39 \cdot 30 + 29 \cdot 33 = 2127$。

SCORING: Input 4: $N \leq 200$, 且所有 $w_i \leq 200$。 Inputs 5-6: 所有 $w_i \leq 200$。 Inputs 7-10: $N \leq 5000$。 Inputs 11-14: 所有 $w_i$ 和 $c_i$ 独立生成，且服从均匀随机分布。 Inputs 15-19: 无额外限制。 题目来源：Benjamin Qi

标签: USACO|2025|Platinum

来源

USACO|2025|Platinum