AT_abc483_d.Glitchy Robot

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There is a robot on a number line. Initially, the robot is at coordinate 00. Also, Takahashi has an integer sequence A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N) of length NN.

Takahashi performs the following steps in order.

  1. Choose at most 11 element of AA and flip its sign. That is, choose 00 or 11 index ii satisfying 1≤i≤N1\leq i\leq N, and replace AiA_i with −Ai-A_i.

  2. Start the robot. After starting, the robot makes NN moves. In the ii-th move (1≤i≤N)(1\leq i\leq N), letting xx be its current coordinate, the robot moves in a straight line to coordinate x+Aix+A_i.

Takahashi wants to maximize the number of integer coordinates that the robot passes through at least once.
Find the maximum possible value of "the number of integer coordinates that the robot passes through at least once" when Takahashi acts optimally.

Here, the robot moves continuously. When a move takes the robot from coordinate SS to coordinate TT, it is considered to have passed through every integer coordinate between SS and TT, inclusive.

数轴上有一个机器人。初始时,机器人位于坐标 00 处。此外,高桥拥有一个长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)。

高桥将按顺序执行以下步骤:

  1. 从 AA 中至多选择 1 个元素并将其符号取反。即:选择 00 或 11 个下标 ii(满足 1≤i≤N1\leq i\leq N),并将 AiA_i 替换为 −Ai-A_i。

  2. 启动机器人。启动后,机器人将进行 NN 次移动。在第 ii 次移动(1≤i≤N1\leq i\leq N)中,设其当前坐标为 xx,则机器人沿直线移动到坐标 x+Aix+A_i。

高桥希望最大化机器人至少经过一次的整数坐标的个数。
当高桥采取最优策略时,求“机器人至少经过一次的整数坐标的个数”的最大可能值。

此处,机器人连续移动。当一次移动将机器人从坐标 SS 移动到坐标 TT 时,认为它经过了 SS 与 TT 之间(含端点)的所有整数坐标。

输入格式

The input is given from Standard Input in the following format:

NN
A1A_1 A2A_2 ⋯\cdots ANA_N

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

NN
A1A_1 A2A_2 ⋯\cdots ANA_N

输出格式

Print the maximum possible value of the number of integer coordinates that the robot passes through at least once when Takahashi acts optimally.

输出当高桥采取最优策略时,机器人至少经过一次的整数坐标点数量的最大可能值。

输入输出样例

  • 输入#1

    3
    -2 3 -2

    输出#1

    8
  • 输入#2

    2
    2 3

    输出#2

    6

说明/提示

Sample 1 Explanation:
Initially, A=(−2,3,−2)A=(-2,3,-2). If Takahashi flips the sign of A2A_2, then A=(−2,−3,−2)A=(-2,-3,-2). In this case, the robot moves as follows.

  • In its 11-st move, the robot moves from 00 to −2-2. The integer coordinates it passes through in this move are −2,−1,0-2,-1,0.
  • In its 22-nd move, the robot moves from −2-2 to −5-5. The integer coordinates it passes through in this move are −5,−4,−3,−2-5,-4,-3,-2.
  • In its 33-rd move, the robot moves from −5-5 to −7-7. The integer coordinates it passes through in this move are −7,−6,−5-7,-6,-5.

Thus, the integer coordinates the robot passes through at least once are the 88 coordinates −7,−6,−5,−4,−3,−2,−1,0-7,-6,-5,-4,-3,-2,-1,0, and this is the maximum possible count, so print 88.

Note that if Takahashi did not flip the sign of any element, the robot would move as 0→−2→1→−10\to -2\to 1\to -1, and the integer coordinates it passes through at least once would be the 44 coordinates −2,−1,0,1-2,-1,0,1.

Sample 2 Explanation:
If no element of AA is changed, the robot moves as 0→2→50\to 2\to 5, and the integer coordinates it passes through at least once are the 66 coordinates 0,1,2,3,4,50,1,2,3,4,5.
This is the maximum possible count, so print 66.

Constraints

  • 1≤N≤2×1051 \leq N \leq 2\times 10^5
  • −109≤Ai≤109-10^9 \leq A_i \leq 10^9
  • Ai≠0A_i\neq 0
  • All input values are integers.

样例 1 解释:
初始时,A=(−2,3,−2)A=(-2,3,-2)。若高桥翻转 A2A_2 的符号,则 A=(−2,−3,−2)A=(-2,-3,-2)。此时机器人按如下方式移动:

  • 在第 11 次移动中,机器人从 00 移动到 −2-2。此次移动经过的整数坐标为 −2,−1,0-2,-1,0。
  • 在第 22 次移动中,机器人从 −2-2 移动到 −5-5。此次移动经过的整数坐标为 −5,−4,−3,−2-5,-4,-3,-2。
  • 在第 33 次移动中,机器人从 −5-5 移动到 −7-7。此次移动经过的整数坐标为 −7,−6,−5-7,-6,-5。

因此,机器人至少经过一次的整数坐标共有 88 个:−7,−6,−5,−4,−3,−2,−1,0-7,-6,-5,-4,-3,-2,-1,0,这是可能的最大值,故输出 88。

注意,若高桥不翻转任何元素的符号,则机器人将按 0→−2→1→−10\to -2\to 1\to -1 移动,此时它至少经过一次的整数坐标仅为 44 个:−2,−1,0,1-2,-1,0,1。

样例 2 解释:
若不对 AA 的任何元素作修改,则机器人将按 0→2→50\to 2\to 5 移动,此时它至少经过一次的整数坐标为 66 个:0,1,2,3,4,50,1,2,3,4,5。
这是可能的最大值,故输出 66。

限制条件

  • 1≤N≤2×1051 \leq N \leq 2\times 10^5
  • −109≤Ai≤109-10^9 \leq A_i \leq 10^9
  • Ai≠0A_i\neq 0
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页