TopCoder

User's AC Ratio

81.8% (9/11)

Submission's AC Ratio

35.7% (10/28)

Tags

Description

在電影節中,有 $N$ 部電影依序被放映,第 $i$ 部電影會帶給你滿足度 $a_i$。每看完一部電影,你可以選擇在緊接下來的時間看這部電影的影評,同樣會給你帶來 $a_i$ 的滿足度,但是你將會錯過下部電影的播放時間。

如果你選擇看影評,你只能在緊連的下一部電影時間看影評,而且你只會錯過下一部電影。如果你看的影評是來自最後放映的電影,則你不會錯過任何電影。請問所能達成最大滿足度為何。

Input Format

輸入第一行是一個整數 $N$ 代表人數。

第二行是 $N$ 個以空白分隔的整數 $a_i$,代表電影依序的滿足度。

輸入保證 $1\le N\le 10^ 5$,$1\le a_i\le 1000$。

Output Format

輸出一行一個整數代表最大可能的滿足度。

Sample Input 1

3
1 5 9

Sample Output 1

24

Sample Input 2

4
5 6 1 3

Sample Output 2

23

Hints

Problem Source

ZeroJudge

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~12 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2