分数: 5 点
问题陈述
给你一个整数序列 A = (A_1, A_2, \dots, A_N) 长度 N.
你还有一个整数 x,最初是 0.
您将执行以下操作 N 操作:
- 对于 i = 1, 2, \dots, N,选择以下三个操作之一:
- 替换 x 与 x + A_i.
- 替换 x 与 \vert x - A_i \vert.
- 什么也不做。
找出 的可能值的数量 x 毕竟 N 操作已完成。
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 2 \times 10^6
- \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 2 \times 10^6
- 所有输入值均为整数
部分分数
此题得分部分。
- 如果您使用以下方法求解数据集 \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 5 \times 10^5,你会得到 4 点。
输入
输入由标准输入给出,格式如下:
N A_1 A_2 \dots A_N
输出
打印可能值的数量 x 毕竟 N 操作已完成。
示例输入 1
3 2 7 5
示例输出 1
10
例如,您可以获得 x = 9 通过执行以下操作:
- 最初, x = 0.
- At i = 1,替换 x 与 \vert x - A_i \vert = \vert 0 - 2 \vert = 2.
- At i = 2,替换 x 与 x + A_i = 2 + 7 = 9.
- At i = 3,什么也不做。 我有一个带有
示例输入 2
10 49 85 36 30 71 65 38 45 73 27
示例输出 2
454