← 返回题目列表

AtCoder · joigsp2025_b

B. 雪球 2

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

配点: 100 点

葵正在雪地里玩耍。 在葵桑面前 N 雪球排成一条直线, 从左边开始 雪球 i 番目 (1 \leqq i \leqq N的大小是 A_i 。从

葵终于实现了一个大目标。 1 我想做两个雪球。 为此,请执行以下一系列操作来制作雪球 1 我决定重复此操作,直到我得到一个或无法再操作它。

  1. 相邻 2 选择一个雪球。此时左边雪球的大小为 l,右侧雪球的大小为 r ,那么 必须是0 \leqq l-r \leqq 1 。
  2. 已选择 2 合并两个雪球。结果我选择了 2 雪球的大小 l+r 雪球 替换为 1 。也就是说,在执行操作之前,先从左边开始计算尺寸。 当 s_1,s_2,\ldots,s_k 的 k 雪球排列起来时,从左边开始 t 番目 (1 \leqq t \leqq k-1)雪球和 当合成第 t+1 个雪球时,左起大小为 s_1,s_2,\ldots,s_{t-1},s_t+s_{t+1},s_{t+2},\ldots,s_k 的 k-1 雪球排成一排。

当给出有关排列雪球的信息时,葵可以通过执行适当的操作来制作雪球。 编写一个程序来判断是否可以制作 1 。 输出


入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

到标准输出 1 行。 葵打雪仗 如果你能做到的话 1 如果你能做到 Yes ,否则 No 。 在第

制約

  • 2 \leqq N \leqq 500\,000.
  • 1 \leqq A_i \leqq 10^{12} (1 \leqq i \leqq N).
  • 所有输入值都是整数。

小課題

  1. (15 点) A_1 = A_2 = \cdots = A_N.
  2. (18 点) N \leqq 8.
  3. (18 点) N \leqq 200.
  4. (19 点) N \leqq 5\,000.
  5. (30 点)没有额外的限制。

入力例 1

5
1 1 1 1 1

出力例 1

Yes

例如,葵通过执行以下操作最终创建了一个雪球。 1 。

  1. 从左起 左边的 4 第 和 选择第 5 个雪球并将其合并。操作后,尺寸从左开始 1,1,1,2 雪球排成一排。
  2. 从左起 左边的 1 第 和 选择第 2 个雪球并将其合并。操作后,尺寸从左开始 2,1,2 雪球排成一排。
  3. 从左起 左边的 1 第 和 选择第 2 个雪球并将其合并。操作后,尺寸从左开始 3,2 雪球排成一排。
  4. 从左起 左边的 1 第 和 选择第 2 个雪球并将其合并。操作后,尺寸从左开始 5 雪球排成一排。

此输入示例满足所有子任务约束。


入力例 2

3
2 2 2

出力例 2

No

无论葵桑如何操纵雪球, 它不能是 1 。

此输入示例满足所有子任务约束。


入力例 3

8
5 4 3 2 1 2 3 4

出力例 3

No

此输入示例是一个小作业。 满足 2,3,4,5 满足约束。 与


入力例 4

16
3 2 1 6 2 1 3 2 1 3 12 6 1 1 1 2

出力例 4

Yes

此输入示例是一个小作业。 满足 3,4,5 满足约束。 与