← 返回题目列表

Codeforces · 1249/E

E. 乘电梯还是楼梯?

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

您计划购买 $$$n$$$ 层楼的公寓。楼层从下到上编号为 $$$1$$$ 到 $$$n$$$。首先,对于每个楼层,您想知道从第一层(底层)到达该楼层的最短总时间。

让:

- $$$a_i$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$ 是使用楼梯从第 $$$i$$$ 层到第 $$$(i+1)$$$ 层(以及从第 $$$(i+1)$$$ 层到第 $$$i$$$ 层所需的时间;
- $$$b_i$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$ 是使用电梯从第 $$$i$$$ 层到第 $$$(i+1)$$$ 层(以及从第 $$$(i+1)$$$ 层到第 $$$i$$$ 层所需的时间,还有一个值$$$c$$$——电梯使用的时间开销(你需要等待,电梯门太慢了!)。

一次,您可以通过两种不同的方式从您所在的 $$$x$$$ 所在楼层前往任何楼层 $$$y$$$ ($$$x \ne y$$$):

- 如果您使用楼梯,只需将 $$$a_i$$$ 的相应值相加即可。正式来说,需要 $$$\sum\limits_{i=min(x, y)}^{max(x, y) - 1} a_i$$$ 时间单位。
- 如果您使用电梯,只需将 $$$c$$$ 和 $$$b_i$$$ 的相应值相加即可。形式上,需要 $$$c + \sum\limits_{i=min(x, y)}^{max(x, y) - 1} b_i$$$ 时间单位。

您可以执行任意数量的移动(可能为零)。

因此,您的任务是为每个 $$$i$$$ 确定从 $$$1$$$-st(底层)楼层到达 $$$i$$$-th 层所需的最短总时间。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le c \le 1000$$$) — 建筑物的楼层数和乘坐电梯的时间开销。

输入的第二行包含 $$$n - 1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 1000$$$),其中 $$$a_i$$$ 是从 $$$i$$$ 层到第 $$$i$$$ 层所需的时间使用楼梯的第 $$$(i+1)$$$ 个(以及从第 $$$(i+1)$$$ 个到第 $$$i$$$ 个)。

输入的第三行包含 $$$n - 1$$$ 整数 $$$b_1, b_2, \dots, b_{n-1}$$$ ($$$1 \le b_i \le 1000$$$),其中 $$$b_i$$$ 是从 $$$i$$$ 层到第 $$$i$$$ 层所需的时间使用电梯第 $$$(i+1)$$$(以及从第 $$$(i+1)$$$ 到第 $$$i$$$)。

输出

打印 $$$n$$$ 整数 $$$t_1, t_2, \dots, t_n$$$,其中 $$$t_i$$$ 是如果你可以执行任意数量的移动,从第一层到达 $$$i$$$ 层的最短总时间。

示例

输入 #1

10 2
7 6 18 6 16 18 1 17 17
6 9 3 10 9 1 10 1 5

输出 #1

0 7 13 18 24 35 36 37 40 45

输入 #2

10 1
3 2 3 1 3 3 1 4 1
1 2 3 4 4 1 2 1 3

输出 #2

0 2 4 7 8 11 13 14 16 17