#2840. 「JOISC 2018 Day 4」糖

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 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

样例输出 1

7
12
10

样例说明 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

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

数据范围与提示

对于全部数据, 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 分。