I am trying to solve this problem on codechef https://www.codechef.com/problems/TRIP.
My code is :- https://ideone.com/ZgA0yr
I am not sure why am I getting TLE. Any help would be great.
P.S: Code is small to go through so please go through it if possible.
Problem can be solved in linear time by using two pointers (well, three actually).
Let DP[i] be the minimum "steps" to reach station i and W[i] be the amount of ways to reach station i in the minimum number of "steps".
Suppose we are at station r. Let l1 be the leftmost station that can reach station r without refueling and l2 be the rightmost station such that DP[l2] = DP[l1]. Then DP[r] = DP[l1] + 1 and . We can calculate that sum in O(1) using prefix sums. Let , then the above formula becomes W[r] = S[l2] - S[l1 - 1].
We start by setting W[1] = 1 and in the end the answer will be DP[N] - 1 (because we're not counting steps but refuels) and W[N].