06761. USACO·浇灌植物 未做

Bessie 的花园中有 $N$ 株植物，从左到右编号为 $1$ 到 $N$（$2\le N\le 5\cdot 10^5$）。Bessie 知道植物 $i$ 至少需要 $w_i$（$0\le w_i\le 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\le i\le N$，计算仅使用前 $i-1$ 条水渠灌溉植物 $1$ 到 $i$ 所需要的最小费用。

输入的第一行包含一个正整数 $N$。

第二行包含 $N$ 个空格分隔的整数 $w_1,\dots ,w_N$。

第三行包含 $N-1$ 个空格分隔的整数 $c_1,\dots ,c_{N-1}$。

输出 $N-1$ 行，每行包含一个整数。第 $i-1$ 行包含使用前 $i-1$ 条水渠灌溉前 $i$ 株植物的最小费用。

【样例解释】

• 测试点 5-6：所有 $w_i\le 200$。

• 测试点 7-10：$N\le 5000$。

• 测试点 11-14：所有 $w_i$ 和 $c_i$ 独立地均匀随机生成。

• 测试点 15-19：没有额外限制。

【数据规模与约定】

• 测试点 4：$N\le 200$，并且所有 $w_i\le 200$。

• 测试点 5-6：所有 $w_i\le 200$。

• 测试点 7-10：$N\le 5000$。

• 测试点 11-14：所有 $w_i$ 和 $c_i$ 独立地均匀随机生成。

• 测试点 15-19：没有额外限制。

供题：Benjamin Qi