分数: 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。在这种情况下,最优策略如下:
- 采取行动 2。我们跑的距离为 1 总共跳跃的距离 1,所以需要 总共 2 \times 1 + 2 \times 1 = 4 秒。
- 采取行动 1。这需要 再次 2 秒。
- 采取行动 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