CF1249E By Elevator or Stairs?

你计划在一栋有 $n$ 层的楼房中购买一套公寓。楼层从下到上编号为 $1$ 到 $n$。首先，你想知道从第一层（底层）到每一层所需的最小总时间。 设： - $a_i$（对于所有 $i$ 从 $1$ 到 $n-1$）表示使用楼梯从第 $i$ 层到第 $i+1$ 层（或从第 $i+1$ 层到第 $i$ 层）所需的时间； - $b_i$（对于所有 $i$ 从 $1$ 到 $n-1$）表示使用电梯从第 $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$，求出从第一层到第 $i$ 层所需的最小总时间。

输入的第一行包含两个整数 $n$ 和 $c$（$2 \le n \le 2 \times 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+1$ 层（或反向）所需的时间。 第三行包含 $n-1$ 个整数 $b_1, b_2, \dots, b_{n-1}$（$1 \le b_i \le 1000$），其中 $b_i$ 表示使用电梯从第 $i$ 层到第 $i+1$ 层（或反向）所需的时间。

输出 $n$ 个整数 $t_1, t_2, \dots, t_n$，其中 $t_i$ 表示从第一层到第 $i$ 层所需的最小总时间（可以进行任意多次移动）。

由 ChatGPT 4.1 翻译