(cache)D - Bonus EXP

Contest Duration: 2024-08-31(Sat) 21:00 - 2024-08-31(Sat) 22:40 (local time) (100 minutes) Back to Home

D - Bonus EXP Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $400$ 点

問題文

高橋君は $N$ 匹のモンスターに順に出会います。 $i$ 匹目 $(1\leq i\leq N)$ のモンスターの強さは $A_i$ です。

高橋君はそれぞれのモンスターについて逃がすか倒すか選ぶことができます。
高橋君はそれぞれの行動によって次のように経験値を得ます。

モンスターを逃がした場合、得られる経験値は $0$ である。
強さが $X$ のモンスターを倒したとき、経験値を $X$ 得る。
ただし、モンスターを倒すのが偶数回目（ $2$ , $4$ , $\ldots$ 回目）であるとき、さらに追加で経験値を $X$ 得る。

$N$ 匹から高橋君が得た経験値の合計としてあり得る最大の値を求めてください。

制約

$1\leq N\leq 2\times 10^5$
$1\leq A_i\leq 10^9$
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $A_2$   $\ldots$   $A_N$

出力

$N$ 匹から高橋君が得た経験値の合計としてあり得る最大の値を整数で出力せよ。

入力例 1Copy

Copy

5
1 5 3 2 7

出力例 1Copy

Copy

$1,2,3,5$ 匹目のモンスターを倒して、 $4$ 匹目のモンスターを逃したとき、高橋君は次のように経験値を得ます。

強さが $A_1=1$ のモンスターを倒す。高橋君は $1$ の経験値を得る。
強さが $A_2=5$ のモンスターを倒す。高橋君は $5$ の経験値を得る。モンスターを倒すのは $2$ 回目であるため、追加で経験値 $5$ を得る。
強さが $A_3=3$ のモンスターを倒す。高橋君は $3$ の経験値を得る。
$4$ 匹目のモンスターを逃がす。高橋君は経験値を得ない。
強さが $A_5=7$ のモンスターを倒す。高橋君は $7$ の経験値を得る。モンスターを倒すのは $4$ 回目であるため、追加で経験値 $7$ を得る。

よって、このとき $1+(5+5)+3+0+(7+7)=28$ の経験値を得ます。
出会ったモンスターであっても、逃がした場合は倒した回数には数えられないことに注意してください。

高橋君がどのように行動しても得られる経験値は $28$ 以下であるため、 $28$ を出力します。
なお、この場合においてすべてのモンスターを倒した時に得られる経験値は $1+(5+5)+3+(2+2)+7=25$ となります。

入力例 2Copy

Copy

2
1000000000 1000000000

出力例 2Copy

Copy

3000000000

答えが $32$ bit 整数型に収まらない可能性があることに注意してください。

Score : $400$ points

Problem Statement

Takahashi will encounter $N$ monsters in order. The $i$ -th monster $(1\leq i\leq N)$ has a strength of $A_i$ .

For each monster, he can choose to either let it go or defeat it.
Each action awards him experience points as follows:

If he lets a monster go, he gains $0$ experience points.
If he defeats a monster with strength $X$ , he gains $X$ experience points.
If it is an even-numbered defeated monster (2nd, 4th, ...), he gains an additional $X$ experience points.

Find the maximum total experience points he can gain from the $N$ monsters.

Constraints

$1\leq N\leq 2\times 10^5$
$1\leq A_i\leq 10^9$
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $A_2$   $\ldots$   $A_N$

Output

Print the maximum total experience points he can gain from the $N$ monsters as an integer.

Sample Input 1Copy

Copy

5
1 5 3 2 7

Sample Output 1Copy

Copy

If Takahashi defeats the 1st, 2nd, 3rd, and 5th monsters, and lets the 4th monster go, he gains experience points as follows:

Defeats a monster with strength $A_1=1$ . He gains $1$ experience point.
Defeats a monster with strength $A_2=5$ . He gains $5$ experience points. As it is the 2nd defeated monster, he gains an additional $5$ points.
Defeats a monster with strength $A_3=3$ . He gains $3$ experience points.
Lets the 4th monster go. Takahashi gains no experience points.
Defeats a monster with strength $A_5=7$ . He gains $7$ experience points. As it is the 4th defeated monster, he gains an additional $7$ points.

Therefore, in this case, he gains $1+(5+5)+3+0+(7+7)=28$ experience points.
Note that even if he encounters a monster, if he lets it go, it does not count as defeated.

He can gain at most $28$ experience points no matter how he acts, so print $28$ .
As a side note, if he defeats all monsters in this case, he would gain $1+(5+5)+3+(2+2)+7=25$ experience points.

Sample Input 2Copy

Copy

2
1000000000 1000000000

Sample Output 2Copy

Copy

3000000000

Beware that the answer may not fit in a $32$ -bit integer.