This is the problem link for which i am getting TLE. I am not able to figure out the fault in my solution . Please look into it. Thank You.
Problem Link : http://www.codechef.com/problems/IGNUS14A
Link to my solution :
My approach to the solution :
I am starting from city 0 so i initialize my variable with the cost of first city . Now from 1st city to last city i am using a dynamic programming approach . I can also skip atmost d-1 cities further from the current ith city and can land to (i+d)th city directly any time . So every time when i am in the ith city i will find out what is the minimum cost to get to that ith city , and for that if i will look into the values of the last d values from the ith element particularly from i-d to i-1 and will find out the minimum value and will add to the cost of ith city .For this i used Segment tree to do it in log(n) time . After that i will update the new value obtained in Segment tree i.e, dp[i] which is minimum value incurred to reach that point so that this will be needed for further city . By doing so , at last , i will get the value of dp[n-1].
Time complexity is O(nlogn) .
But even then i am doing some error which is giving a TLE verdict . Please look into it .