← 返回题目列表

AtCoder · arc189_d

D. 高桥是史莱姆

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

分数: 700 点

问题陈述

有 N 史莱姆从左到右排成一排。 对于 i = 1, 2, \ldots, N, i左边第一个史莱姆有尺寸 A_i.
对于每个 K = 1, 2, \ldots, N,解决以下问题。

高桥是 K初始状态下从左边算起的第一个史莱姆。 求出在执行以下操作任意次数后他可以拥有的最大尺寸,可能为零:

  • 选择一个与他相邻且严格小于他的史莱姆,并将其吸收。 结果,吸收的粘液消失,高桥的体型随着吸收的粘液的大小而增大。

当史莱姆因吸收而消失时,间隙立即闭合,并且与消失的史莱姆相邻的史莱姆(如果存在)变得相邻(参见示例输入 1 中的说明)。

约束

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印答案 B_K 对于每个 K = 1, 2, \ldots, N,以空格分隔,格式如下:

B_1 B_2 \ldots B_N

示例输入 1

6
4 13 2 3 2 6

示例输出 1

4 30 2 13 2 13

作为一个例子,考虑这个问题 K = 4。 我们将参考剩余史莱姆的尺寸,从左到右列出,其中高桥的尺寸括在方括号中 [ ],作为 行的状态。 也就是说,初始状态是 (4, 13, 2, [3], 2, 6)。考虑一下高桥的以下一系列行动。

  • 他吸收了右边的粘液。结果,吸收的粘液消失了,他的尺寸变成了 3 + 2 = 5。状态变成 (4, 13, 2, [5], 6).
  • 他吸收了左边的粘液。结果,吸收的粘液消失了,他的尺寸变成了 5 + 2 = 7。状态变成 (4, 13, [7], 6).
  • 他吸收了右边的粘液。结果,吸收的粘液消失了,他的尺寸变成了 7 + 6 = 13。状态变成 (4, 13, [13]).

与他相邻的史莱姆没有严格小于他的,因此他无法执行任何更多动作。他的最终尺寸是 13,这是可能的最大值。


示例输入 2

12
22 25 61 10 21 37 2 14 5 8 6 24

示例输出 2

22 47 235 10 31 235 2 235 5 235 6 235