← 返回题目列表

AtCoder · agc007_d

D. 希克和游戏

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

分数: 1200 点

问题陈述

想象一下在线游戏。最初,玩家位于位置 0 与 N 糖果在他手中,出口位于 位置 E。还有 N 游戏中的熊。的 i- 第熊位于 x_i。玩家的最大移动速度为 1 而熊根本不动。

当玩家给小熊糖果时,小熊会在之后提供一枚硬币 T 时间单位。更具体地说,如果 i第-只熊在某个时间得到了一颗糖果 t,它会在该时间的位置放一枚硬币 t+T。这个游戏的目的是给所有的小熊糖果,捡起所有的硬币,然后走到出口。请注意,只有当玩家处于与熊完全相同的位置时,玩家才能给熊糖果。此外,每只熊只能生产一次硬币。如果玩家在硬币被放下之后或恰好同时访问了硬币的位置,则玩家可以捡起硬币。硬币在被玩家收集之前不会消失。

Shik 是这个游戏的专家。他可以给熊糖果并立即捡起硬币。您将获得游戏的配置。请计算 Shik 收集所有硬币并到达出口所需的最短时间。

约束

  • 1 \leq N \leq 100,000
  • 1 \leq T, E \leq 10^9
  • 0 < x_i < E
  • x_i < x_{i+1} 为 1 \leq i < N
  • 所有输入值均为整数。

部分分数

  • 在测试用例中值得 600 点, N \leq 2,000.

输入

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

N E T
x_1 x_2 ... x_N

输出

打印一个表示答案的整数。


示例输入 1

3 9 1
1 3 8

示例输出 1

12

最佳策略是在治疗完每只熊后等待硬币。总共花费的等待时间为 3 移动是 9。所以答案是 3 + 9 = 12.


示例输入 2

3 9 3
1 3 8

示例输出 2

16

示例输入 3

2 1000000000 1000000000
1 999999999

示例输出 3

2999999996