레이팅 미적용농부 존(Farmer John)은 전국 횡단 휴가를 떠나기로 했고, 큰 트럭을 빌려 소들도 데려가고 싶어 한다!
트럭에는 최대 G 단위 (1 <= G <= 1,000,000)의 연료를 담을 수 있는 큰 탱크가 있다. 안타깝게도 연비가 몹시 나빠서, 거리 1단위를 이동할 때마다 연료 1단위를 소모한다. FJ가 경로를 따라 이동해야 하는 총거리는 D 단위 (1 <= D <= 1,000,000,000)이다.
FJ는 아마 탱크를 채우기 위해 여러 번 멈춰야 할 것이므로, 경로를 따라 있는 N개 (1 <= N <= 50,000)의 주유소 목록을 만들었다. 각 주유소 i에 대해, 경로 시작점으로부터의 거리 X_i (0 <= X_i <= D)와 그 주유소가 파는 연료의 단위당 가격 Y_i (1 <= Y_i <= 1,000,000)를 기록했다.
이 정보와 FJ가 정확히 B 단위 (0 <= B <= D)의 연료를 가지고 여정을 시작한다는 사실이 주어질 때, FJ가 목적지에 도달하기 위해 연료에 지불해야 하는 최소 금액을 구하시오. 목적지에 도달하는 것이 불가능하면 -1을 출력한다. 답이 표준 32비트 정수에 담기지 않을 수 있음에 유의하라.
첫째 줄: 공백으로 구분된 네 정수 N, G, B, D.
둘째 줄부터 1+N번째 줄까지: 각 줄에 주유소 i를 설명하는 두 정수 X_i와 Y_i가 주어진다.
FJ가 목적지에 도달하기 위해 지불해야 하는 최소 비용, 목적지에 도달할 실현 가능한 방법이 없으면 -1.
fuel.in · 출력을 쓸 파일 fuel.out4 10 3 17
2 40
9 15
5 7
10 12174Output details: FJ buys 2 units at station 1 (cost 80), fills up at station 3 (cost 70), and buys 2 units at station 4 (cost 24), for total 174.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > US Open > Silver