← 返回题目列表

AtCoder · agc050_b

B. 三枚硬币

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

N 单元格排列成一行。 单元格已编号 1 通过 N 从左到右。

最初,所有单元格都是空的。 您可以以任意顺序执行任意次数的以下两种类型的操作:

  • 选择三个 连续 清空单元格,并在三个单元格中各放一枚硬币。
  • 选择三个 连续 装有硬币的单元格,然后移除所选单元格上的所有三个硬币。

执行完操作后,如果 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 和一个没有硬币的电池 . (一个点)。 一种最佳方式如下:

.... \rightarrow .ooo

我们得到 2 + 3 + 4 = 9 指的是这个方向。


示例输入 2

6
3
-2
-1
0
-1
4

示例输出 2

6

一种最佳方式如下:

...... \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