No.1037 exhausted
タグ : / 解いたユーザー数 156
作問者 :
ngtkana
/ テスター :
tempura_pp
Problem Statement
Yukiko's car consumes 1 unit of fuel for every 1 unit of distance traveled. Yukiko drives this car along a road of length $L$ to go to the supermarket. Initially, the car's tank is full , holding $ V $ units of gasoline. There are $ N $ gas stations along the road, where she can refuel.
Each gas station $i$ has a fixed position (distance from the starting point) $x_i$, an amount of fuel it can supply $v_i$, and a refueling cost $w_i$. When Yukiko arrives at this gas station, by paying a fixed cost independent of the amount $w_i$, she can refill up to $v_i$ units of gasoline. However, she cannot refill so that the contents of the fuel tank exceed the maximum capacity. Also, Yukiko has no return trip.
Find the minimum cost required for Yukiko to get to the supermarket.
Addendum
2020-04-24 21:44 You cannot move in the direction of decreasing coordinates.
2020-04-24 21:45 You cannot pay the cost multiple times at the same gas station to refuel multiple times.
2020-04-24 22:07 Gasoline and fuel refer to the same thing.
2020-04-24 22:09 The Output section previously said to output the minimum fuel; this has been corrected to the minimum cost.
2020-04-24 22:17 "She cannot refill so that the contents of the fuel tank exceed the maximum capacity" means that when the current remaining amount is x and she refills v_i, the remaining amount after refilling becomes min(V,x+v_i).
Input
$N\ V\ L$
$x_0\ v_0\ w_0$
$\dots$
$x_{N - 1}\ v_{N - 1}\ w_{N - 1}$
The first line contains the number of gas stations $N$, the capacity of the fuel tank (= the initial amount of fuel) $V$, and the total length of the course $L$, separated by spaces. The following $N$ lines give the information on the gas stations. The information on the $i$-th gas station consists of three values: the distance of its location from the start $x_i$, the amount of gasoline it can supply$ v_i$, and the cost required to refuel $w_i$, separated by spaces.
The input satisfies the following constraints.
- $1 \leq N \leq 2000$
- $1 \leq V \leq 2000$
- $1 \leq L \leq 10 ^ 9 $
- $0 \leq x_0 \leq x_1 \leq \dots \leq x_{N - 1} \leq L$
- $0 \leq v_i \leq 10 ^ 9$
- $0 \leq w_i \leq 10 ^ 9$
Output
Output the minimum cost required to reach the goal on one line. However, if it is impossible to reach the goal, output '-1'.
Sample
Sample 1
Input
3 5 10 2 4 2 3 3 3 8 2 4
Output
7
There are 3 gas stations in total, at positions 2, 3, 8. In this case, let's refuel at positions 3, 8 and reach the goal. Refueling at position 2 looks like it would give a lot of gasoline, but the tank holds at most 5, the same as the initial amount, so it isn't very helpful. Rather, since the distance from position 3 to position 8 is 5, we can see that she must refuel at least at both of these.
Sample 2
Input
2 5 10 0 20 0 10 20 0
Output
-1
There are gas stations only at the start and at the goal. How sad.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。