I solved it in the following manner: First sort the petrol pumps in ascending order of x let f[i] denote the minimum amount of money to be paid when we reach the ith petrol pump. We can get that f[i]=c[i]+min(f[j] such that x[i]-x[j]<=d) This will take upto n^2 operations. To speed up we can use a segment tree and find out the minimum cost of all petrol pumps in the range [x[i]-d,x[i]-1]. As x[i]<=10^9,we can precompute the left most petrol pump reachable for each i in one pass of the array. This approach takes nlogn operations. My submission:http://www.codechef.com/viewsolution/7351279

you can also solve it in O(nlogn) using set.

The naive DP approach to solve this is O(N ^ 2) Time complexity where DP[i] denotes the least money to be spent to reach ith position . And for calculating dp[i] , we have to do a range minimum query from dp[i] to dp[j] where j is the least index such that the jth position >= ith position — D . So we can use a segment tree to speed this up to O(nlogn). http://www.codechef.com/viewsolution/7353139