← 返回题目列表

AtCoder · agc030_b

B. 烧树

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

分数: 800 点

问题陈述

高桥湖的周长为 L。在湖的周围,有湖的主人高桥的住宅。 湖圆周上的每个点都有一个坐标 0 和 L (包括 0 但不是 L),这是距高桥住所的距离,逆时针测量。

有 N 湖周围的树木;的坐标 i- 第棵树是 X_i。坐标处没有树 0,高桥的住所所在地。

从住所开始,高桥将重复以下动作:

  • 如果所有树木都被烧毁,则终止该过程。
  • 指定方向:顺时针或逆时针。
  • 沿着指定方向绕湖行走,直到第一次到达尚未被烧毁的树的坐标。
  • 当到达树的坐标时,烧毁那棵树,停留在该位置并返回第一步。

求高桥在此过程中可能行走的最长总距离。

部分分数

此问题可以获得部分分数: 通过满足以下条件的输入将获得

  • 300 积分 N \leq 2000.

约束

  • 2 \leq L \leq 10^9
  • 1 \leq N \leq 2\times 10^5
  • 1 \leq X_1 < ... < X_N \leq L-1
  • 输入中的所有值都是整数。

输入

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

L N
X_1
:
X_N

输出

打印高桥在此过程中可能行走的最长总距离。


示例输入 1

10 3
2
7
9

示例输出 1

15

高桥走过的距离 15 如果流程如下:

  • 步行距离 2 逆时针方向,烧毁坐标处的树 2 并留在那里。
  • 步行距离 5 逆时针方向,烧毁坐标处的树 7 并留在那里。
  • 步行距离 8 顺时针方向,烧毁坐标处的树 9 并留在那里。

示例输入 2

10 6
1
2
3
6
7
9

示例输出 2

27

示例输入 3

314159265 7
21662711
77271666
89022761
156626166
160332356
166902656
298992265

示例输出 3

1204124749