Bonus EXP

题目描述

Takahashi 将按顺序遇到 $N$ 只怪物。第 $i$ 只怪物 $(1\leq i\leq N)$ 的强度为 $A_i$。 对于每只怪物，他可以选择放走或击败它。
每种行为会给予他如下经验点数：

如果他放走一只怪物，他获得 $0$ 经验点。 如果他击败强度为 $X$ 的怪物，他获得 $X$ 经验点。
如果这是被击败的第偶数只怪物（第 2、第 4、……），他额外再获得 $X$ 经验点。

求他从这 $N$ 只怪物中可以获得的最大总经验点数。

输入格式

输入从标准输入给出，格式如下： $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出他可以从 $N$ 只怪物中获得的最大总经验点数，作为一个整数。

5
1 5 3 2 7

28

2
1000000000 1000000000

3000000000

提示

$1\leq N\leq 2\times 10^5$ $1\leq A_i\leq 10^9$ 所有输入值均为整数。如果 Takahashi 击败第 1、2、3 和 5 只怪物，而放走第 4 只怪物，他获得的经验点如下：

击败强度为 $A_1=1$ 的怪物。他获得 $1$ 经验点。 击败强度为 $A_2=5$ 的怪物。他获得 $5$ 经验点。由于这是第 2 只被击败的怪物，他额外获得 $5$ 点。 击败强度为 $A_3=3$ 的怪物。他获得 $3$ 经验点。 放走第 4 只怪物。Takahashi 未获得经验点。 击败强度为 $A_5=7$ 的怪物。他获得 $7$ 经验点。由于这是第 4 只被击败的怪物，他额外获得 $7$ 点。

因此，在此情况下，他获得 $1+(5+5)+3+0+(7+7)=28$ 经验点。
注意即便他遇到怪物，如果他放走它，这只怪物不计入被击败的数量。 无论他如何行动，最多可获得 $28$ 经验点，因此输出 $28$。
顺便一提，如果在此例中他击败所有怪物，他将获得 $1+(5+5)+3+(2+2)+7=25$ 经验点。
注意答案可能超出 32 位整数范围。

标签: AtCoder|abc369D

来源

AtCoder|abc369D