Type: Default 2000ms 512MiB

蛇形走位

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

你将会进行 nn 次移动,在第 ii 次移动中,你可以选择向正方向或负方向移动,距离是 ℓi\ell_i。

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

输入描述

第一行为一个整数 nn,表示移动次数,满足 1⩽n⩽201\leqslant n\leqslant 20。

第二行 nn 个空格隔开的整数 ℓi\ell_i,表示每次移动的距离,满足 1⩽ℓi⩽1×1091\leqslant \ell_i\leqslant 1\times 10^9。

输出描述

求经过原点最大次数。

样例

5
2 5 2 2 1
4
5
100 1 2 3 4
1