← 返回题目列表

AtCoder · ndpc2026_k

K. 加法和减法

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

分数: 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