K. 蛇形走位

传统题

2000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你正在参加国际穿越原点大赛(International Crossing Pivot Contest, ICPC)，场上有一个数轴，开始时，你在数轴 0.5 的位置处。

你将会进行 $n$ 次移动，在第 $i$ 次移动中，你可以选择向正方向或负方向移动，距离是 $\ell_i$ 。

你需要最大化经过原点最大次数。

第一行为一个整数 $n$ ，表示移动次数，满足 $1\leqslant n\leqslant 20$ 。

第二行 $n$ 个空格隔开的整数 $\ell_i$ ，表示每次移动的距离，满足 $1\leqslant \ell_i\leqslant 1\times 10^9$ 。

求经过原点最大次数。

5
2 5 2 2 1

5
100 1 2 3 4