← 返回题目列表

AtCoder · awtf2024_c

C. 燃油

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

分数: 1500 点

问题陈述

解决以下问题 T 测试用例。

您当前位于坐标 0 在数轴上,并且您想要到达坐标 L.

您将使用汽车进行移动。这辆车使用两种燃料: 类型 1 和 2。对于每种类型,汽车都有一个该类型的油箱,容量为 C 升。目前,两个油箱都已满。汽车可以消耗 x 升任一类型的燃料(其中 x 是任何不超过剩余燃料的正整数)移动 x 数轴上任意方向的单位。您可以选择每次运动使用哪种燃料。

有 N 数线上的加油站。的 i-第加油站位于坐标 X_i。当汽车正好位于坐标处时 X_i,您可以购买类型-K_i 燃料费用为 1 每升。当然,您购买的燃油不能超过油箱容量所允许的数量。

判断是否可以到达坐标 L。如果可能的话,找出购买燃料的最低总成本。

约束

  • 1 \leq T \leq 250000
  • 1 \leq N \leq 5000
  • 1 \leq L \leq 10^9
  • 1 \leq C \leq 10^9
  • 0 < X_1 < X_2 < \cdots < X_N < L
  • K_i=1 or 2
  • 总和 N^2 跨单个输入的所有测试用例不超过 5000^2.
  • 所有输入值均为整数。

输入

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

T
case_1
case_2
\vdots
case_T

每个测试用例均按以下格式给出:

N L C
X_1 X_2 \cdots X_N
K_1 K_2 \cdots K_N

输出

打印 T 行。 在 i第行,用于 i- 第一个测试用例,打印 -1 如果无法到达坐标 L,并打印购买燃料的最低总成本。


样本输入 1

5
1 10 4
7
1
1 10 6
7
1
2 12 3
5 7
1 1
2 12 3
5 7
1 2
20 749013197 23809523
46981984 70791437 118235723 132421762 180040807 203849360 251468335 275277857 322889975 346699150 394318091 418113855 465732891 489532137 537144103 558852533 606466719 630275002 677584754 701394209
1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 1 1 2 1 2

示例输出 1

2
0
-1
6
585545066743659

让我们解释一下第一个测试用例。 您可以到达坐标 L 成本为 2 如下:

  • 消耗 3 升型-1 从坐标移动的燃料 0 to 3。剩下的类型——1 燃料是 1 升。
  • 消耗 4 升型-2 从坐标移动的燃料 3 to 7。剩下的类型——2 燃料是 0 升。
  • 购买 2 升型-1 在加油站加油。剩下的类型——1 燃料是 3 升。
  • 消耗 3 升型-1 从坐标移动的燃料 7 to 10。剩下的类型——1 燃料是 0 升。

无法到达坐标 L 成本低于 2。因此,答案是 2.