/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
N 個のマスが一列に並んでおり、左から右に 1 から N までの番号が振られています。
はじめ、すべてのマスは空です。 あなたは、以下の 2 種類の操作を任意の順に何度でも行うことができます。
- 連続する 3 マスであってコインが置かれていないものを選び、それぞれにコインを置く。
- 連続する 3 マスであっていずれにもコインが置かれているものを選び、それぞれからコインを取り除く。
操作を済ませた後、左から i マス目にコインが置かれているなら、a_i 点が得られます。 コインがあるマス全てから得られる点数の合計が、あなたの得点です。
得られる最高得点を求めてください。
制約
- 3 \leq N \leq 500
- -100 \leq a_i \leq 100
- 入力中の全ての値は整数である。
入力
入力は標準入力から以下の形式で与えられる。
N a_1 a_2 : a_N
出力
答えを出力せよ。
入力例 1
4 1 2 3 4
出力例 1
9
コインが置かれたマスを o で、置かれていないマスを . で表します。
最適な手順の 1 つは次の通りです。
.... \rightarrow .ooo
このようにすれば、2 + 3 + 4 = 9 点を得られます。
入力例 2
6 3 -2 -1 0 -1 4
出力例 2
6
最適な手順の 1 つは次の通りです。
...... \rightarrow ooo... \rightarrow oooooo \rightarrow o...oo
このようにすれば、3 + (-1) + 4 = 6 点を得られます。
入力例 3
10 -84 -60 -41 -100 8 -8 -52 -62 -61 -76
出力例 3
0
Score : 800 points
Problem Statement
N cells are arranged in a row. The cells are numbered 1 through N from left to right.
Initially, all cells are empty. You can perform the following two types of operation arbitrary number of times in arbitrary order:
- Choose three consecutive empty cells, and put a coin on each of the three cells.
- Choose three consecutive cells with coins, and remove all three coins on the chosen cells.
After you finish performing operations, if the i-th cell contains a coin, you get a_i points. Your score is the sum of all points you get from the cells with coins.
Compute the maximum possible score you can earn.
Constraints
- 3 \leq N \leq 500
- -100 \leq a_i \leq 100
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 a_2 : a_N
Output
Print the answer.
Sample Input 1
4 1 2 3 4
Sample Output 1
9
We represent a cell with a coin as o and a cell without a coin as . (a dot).
One optimal way is as follows:
.... \rightarrow .ooo
We get 2 + 3 + 4 = 9 points this way.
Sample Input 2
6 3 -2 -1 0 -1 4
Sample Output 2
6
One optimal way is as follows:
...... \rightarrow ooo... \rightarrow oooooo \rightarrow o...oo
We get 3 + (-1) + 4 = 6 points this way.
Sample Input 3
10 -84 -60 -41 -100 8 -8 -52 -62 -61 -76
Sample Output 3
0