How to find the minimum cost fuel required to go from one place to another

Question

The question:
We want to go from a location to another which is D (D <= 1,000,000,000) units away from it by truck. The truck can hold upto G (G < 1,000,000) units of fuel and it consumes 1 unit of fuel for 1 unit distance. There are N (N <= 50,000) fuel stations along the way. Every station i is X_i units away from the start and the price per unit of fuel is Y_i (Y_i <= 1,000,000). We start the journey with B units of fuel. What is the minimum cost way to reach the destination?

(Actual problem statement from a USACO past contest)

My algorithm:
Let F[i] = The minimum cost required to reach fuel station i and the N+1th fuel station is the destination.
Suppose k is the last station where we fill the tank before reaching i, F[i] = F[k] + Y_k * (X_i-X_k). We try this for all the k < i, such that X_i-X_k < D and take the minimum one.
F[N+1] will be the final answer.

The problems with this algorithm:
1. It will take O(N²) time which will not run within the time limits of 2 seconds.
2. It dosent consider the case where we reach a fuel station k with already m units of fuel and we only fill X_i-X_k-m units of fuel to reach i.

How do I overcome these problems?

Answer 1

The contest has official solutions published for all 9 problems:

http://www.usaco.org/index.php?page=open13problems