← 返回题目列表

AtCoder · past202005_h

H. 跨栏

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

分数: 6 点

警告

2020 年 6 月 6 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

Snuke 将在数轴上跑过障碍。 他将从坐标开始 0 并在坐标处完成 L。 有 N 数轴上的障碍,以及 i左边第一个障碍物位于坐标处 x_i. (0 < x_1 < x_2 < \cdots < x_N < L 成立。)

Snuke可以重复选择以下三个动作之一并执行:

  • 行动 1: 跑的距离 1.
  • 行动 2: 跑的距离 0.5,跳跃的距离 1,跑的距离 0.5,总距离为 2.
  • 行动 3: 跑的距离 0.5,跳跃的距离 3,跑的距离 0.5,总距离为 4.

Snuke 的速度为 1 每单位距离 运行时 T_1 秒,以及 在空中时 1 每单位距离 运行时 T_2 秒。 然而,如果 Snuke 在坐标上 x 当他不在空中并且坐标处有障碍物时 x,需要额外 T_3 秒过去了该点。在这里, T_1, T_2,和 T_3 是偶数。

找出 Snuke 在通过坐标之前需要的最短秒数 L。 (如果他跳过坐标 L,我们考虑他经过坐标的时间 L 在空中。)我们可以证明答案是一个整数。

约束

  • 输入中的所有值都是整数。
  • 2 \leq L \leq 10^5
  • 1 \leq N < L
  • 0 < x_1 < x_2 < \cdots < x_N < L
  • 2 \leq T_1, T_2, T_3\leq 1000
  • T_1, T_2,和 T_3 是偶数。

输入

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

N L
x_1 x_2 \cdots x_N
T_1 T_2 T_3

输出

打印 Snuke 在通过坐标之前需要的最小秒数 L,作为整数。 (可以证明这个数是一个整数。)


示例输入 1

2 5
1 4
2 2 20

示例输出 1

10

坐标有障碍 1 和 4。在这种情况下,最优策略如下:

  1. 采取行动 2。我们跑的距离为 1 总共跳跃的距离 1,所以需要 总共 2 \times 1 + 2 \times 1 = 4 秒。
  2. 采取行动 1。这需要 再次 2 秒。
  3. 采取行动 3,在此期间我们传递坐标 L=5。在我们通过这一点之前,我们跑的距离 0.5 并跳跃的距离 1.5,所以需要 总共 2 \times 0.5 + 2 \times 1.5 = 4 秒。

该最优策略所花费的时间是 总共 4 + 2 + 4 = 10 秒,所以我们应该打印 10.


示例输入 2

4 5
1 2 3 4
2 20 100

示例输出 2

164

示例输入 3

10 19
1 3 4 5 7 8 10 13 15 17
2 1000 10

示例输出 3

138