問題一覧 > 通常問題

No.1037 exhausted

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 156
作問者 : ngtkana / テスター : tempura_pp
お気に入りにしたユーザー ProblemId : 3502 / 自分の提出
問題文最終更新日: 2020-04-24 22:17:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 245 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。