← 返回题目列表

AtCoder · abc453_c

E. 偷看

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

分数: 300 点

问题陈述

高桥在坐标 数轴上的 0.5 。

他将使 N 移动。
在 i第一步,他选择正方向或负方向,然后移动 L_i 朝那个方向。

他最多可以通过坐标多少次 0?
在这个问题的约束下,没有移动会在坐标处结束 0.

约束

  • 1 \le N \le 20
  • 1 \le L_i \le 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
L_1 L_2 \dots L_N

输出

输出答案。


示例输入 1

5
2 5 2 2 1

示例输出 1

4

例如,通过选择如下运动方向,他可以通过坐标 0 四次,这是最大值。

  • 在第一次移动中,选择负方向并移动 2。他从坐标移动 0.5 to -1.5,通过坐标 0.
  • 第二次移动时,选择正方向并移动 5。他从坐标移动 -1.5 to 3.5,通过坐标 0.
  • 第三步,选择负方向并移动 2。他从坐标移动 3.5 to 1.5.
  • 第四步,选择负方向并移动 2。他从坐标移动 1.5 to -0.5,通过坐标 0.
  • 第五步,选择正方向并移动 1。他从坐标移动 -0.5 to 0.5,通过坐标 0.

示例输入 2

5
100 1 2 3 4

示例输出 2

1

示例输入 3

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

示例输出 3

20