2840 「JOISC 2018 Day 4」糖

内存限制:512 MB 时间限制:5000 ms

题目描述

译自 JOISC 2018 Day4 T1「飴 / Candies」

桌子上有 $N$ 块糖排成一排。每块糖都有一个「美味度」,从左数第 $i$ 块糖有一个美味度 $A_i$。

JOI 酱决定吃掉这 $N$ 块糖之中的一些糖,并想最大化她要吃的糖的美味度之和。

然而,JOI 酱认为只是贪心地选糖吃没有意思,所以她制定了以下规则:不能同时吃连续的两块糖。

JOI 酱没有决定她要吃多少块糖,所以 JOI 酱想知道,对于每一个 $j\ (1\le j\le \left\lceil \frac{N}{2} \right\rceil)$,当她吃 $j$ 块糖时获得的美味度之和的最大值是多少。这里 $\lceil x\rceil$ 是大于等于 $x$ 的最小整数。

任务

给出糖果数目和每块糖的美味度,写一个程序计算,对于每一个 $j\ (1\le j\le \left\lceil \frac{N}{2} \right\rceil)$,当她吃 $j$ 块糖时获得的美味度之和的最大值是多少。

输入格式

从标准输出读入以下数据: - 第一行包含一个正整数 $N$,表示桌子上有 $N$ 块糖; - 接下来 $N$ 行,第 $i$ 行包含一个正整数 $A_i$。表示从左向右数第 $i$ 块糖的美味度为 $A_i$。

输出格式

输出 $\left\lceil \frac{N}{2} \right\rceil$ 行,第 $j$ 行输出当她吃 $j$ 块糖时获得的美味度之和的最大值。

样例 1

在样例一中,有 $5$ 块糖,从左往右的每块糖美味度分别为 $3,5,1,7,6$。

JOI 酱应按如下方法吃糖:

  • 当她吃 $1$ 块糖时,她应该吃第 $4$ 块(美味度为 $7$);
  • 当她吃 $2$ 块糖时,她应该吃第 $2$ 块和第 $4$ 块(美味度为 $5,7$);
  • 当她吃 $3$ 块糖时,她应该吃第 $1,3,5$ 块(美味度为 $3,1,6$)。

再一次提醒,她不能同时吃连续的两块糖。例如,当她吃两块糖时,她不能同时吃从左往右数第 $4$ 块和第 $5$ 块糖(美味度为 $7,6$)。

样例 2

数据范围与提示

对于全部数据,$1\le N\le 2\times 10^5,1\le A_i\le 10^9$。

对于子任务 $1$,$N\le 2\times 10^3$。若通过可以获得 $8$ 分。

对于子任务 $2$,无附加限制。若通过可以获得 $92$ 分。

样例

样例输入 1

5 3 5 1 7 6

样例输出 1

7 12 10

样例输入 2

20 623239331 125587558 908010226 866053126 389255266 859393857 596640443 60521559 11284043 930138174 936349374 810093502 521142682 918991183 743833745 739411636 276010057 577098544 551216812 816623724

样例输出 2

936349374 1855340557 2763350783 3622744640 4439368364 5243250666 5982662302 6605901633 7183000177 7309502029