分数: 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.