CF1500F Cupboards Jumps

在 Krosh 曾经居住的房子里，有 $n$ 个橱柜排成一行，第 $i$ 个橱柜的高度为 $h_i$。Krosh 最近搬家了，但他没能把橱柜带走。现在他想买 $n$ 个新橱柜，使它们看起来尽可能像原来的橱柜。 Krosh 不记得橱柜的具体高度，但对于每三个连续的橱柜，他记得其中最高和最低橱柜的高度差。换句话说，如果橱柜的高度为 $h_1, h_2, \ldots, h_n$，那么 Krosh 记得所有 $1 \leq i \leq n-2$ 的 $w_i = \max(h_{i}, h_{i+1}, h_{i+2}) - \min(h_{i}, h_{i+1}, h_{i+2})$ 的值。 Krosh 想买 $n$ 个橱柜，使得所有 $w_i$ 的值都与记忆中的一致。请你帮他确定这些橱柜的高度，或者判断他记错了，没有符合条件的高度序列。

第一行包含两个整数 $n$ 和 $C$（$3 \leq n \leq 10^6$，$0 \leq C \leq 10^{12}$）——橱柜的数量和 $w_i$ 的可能最大值。 第二行包含 $n-2$ 个整数 $w_1, w_2, \ldots, w_{n-2}$（$0 \leq w_i \leq C$）——题目中定义的值。

如果不存在符合条件的 $n$ 个橱柜，请输出 “NO”。 否则，第一行输出 “YES”，第二行输出 $n$ 个整数 $h'_1, h'_2, \ldots, h'_n$（$0 \leq h'_i \leq 10^{18}$）——从左到右每个橱柜的高度。 可以证明，如果有解，则一定存在满足高度限制的解。 如果有多组解，输出任意一组均可。

考虑第一个样例： - $w_1 = \max(4, 8, 8) - \min(4, 8, 8) = 8 - 4 = 4$ - $w_2 = \max(8, 8, 16) - \min(8, 8, 16) = 16 - 8 = 8$ - $w_3 = \max(8, 16, 20) - \min(8, 16, 20) = 20 - 8 = 12$ - $w_4 = \max(16, 20, 4) - \min(16, 20, 4) = 20 - 4 = 16$ - $w_5 = \max(20, 4, 0) - \min(20, 4, 0) = 20 - 0 = 20$ 还有其他可能的解，例如：$0, 1, 4, 9, 16, 25, 36$。 由 ChatGPT 4.1 翻译