← 返回题目列表

AtCoder · pakencamp_2018_day3_d

D. 渚酱的别墅

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

配点: 100 点

問題文

渚的别墅是 N 房间和 N-1 由一条书籍通道组成,每个房间都有 1 从 N ,每个过道都有 编号 1 从 N-1 已分配。i 第一段是一个房间 i 和房间 i+1 双向连接,整数 写入 C_i 。

彩叶酱今天早上在这所房子内的一个房间里醒来。身为忍者的彩羽决定使用忍术逃跑。彩羽酱的情绪用一个整数来表示,这个数字越高,她的忍术成功的可能性就越大。心情的价值是开始 0 和段落 i 当你走过它的时候,你的感觉很好。 C_i ,但该机制将启动,你将无法通过该通道。
起始房间 r 和段落 0 多次访问最喜欢的房间后停在该房间时的最大心情 比方说 X_r 。
所有房间 对于 i 查找 X_i 。

入力

输入是按以下格式从标准输入给出的。

N
C_1
C_2
C_3
...
C_{N-1}

出力

总而言之 请输出 N 行。
i 在线 写在方格 X_i ,即房间 请打印从 i 开始时您的心情最大值。


制約

  • 2 \leq N \leq 100000
  • -10^9 \leq C_i \leq 10^9

小課題

小課題 1 [15 点]

  • N \leq 1000 很满意。 您将获得
  • 全部 对于 C_i 是 仅由 0 就是这样。

小課題 2 [30 点]

  • 全部 对于 C_i 是 仅由 0 就是这样。

小課題 3 [55 点]

  • 没有其他限制。

入力例 1

5
70
10
50
20

出力例 1

150
80
80
130
150

在此示例输入中,别墅的图如下所示:

例如,一个房间 3 开始, 通过路线3 → 2 → 1 前往房间 当我停在 1 时,我感觉 您将得到 10 + 70 = 80 。
没有比这更好的感觉了。


入力例 2

8
70
10
-2000
10000
-2000
50
20

出力例 2

8080
8010
8000
10000
10000
8000
8050
8070

该输入是 1, 2 不满足约束。


入力例 3

7
-45
-45
-45
-45
-45
-45

出力例 3

0
0
0
0
0
0
0