A90523.「USACO 2025.1 Platinum」Watering the Plants

题目来自 USACO 2025 January Contest, Platinum Problem 3. Watering the Plants

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

Bessie 有一个十分古怪的灌溉系统，包含 $N-1$ 条水渠，编号为 $1$ 到 $N-1$。每条水渠 $i$ 有一个相关的单位费用 $c_i$（$1\le c_i\le 10^6$），Bessie 可以支付费用 $c_i k$ 来为植物 $i$ 和 $i+1$ 各提供 $k$ 单位的水，其中 $k$ 是一个非负整数。

Bessie 很忙，可能没有时间使用所有的水渠。对于每一个 $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$ 株植物的最小费用。