# getting TLE in IGNUS14A!

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.

http://www.codechef.com/viewsolution/3481438

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 .
Thank You.

Use an O(n) algorithm which finds minimum of every consecutive d-elements window. You can use a deque for this.
I tried segment tree too initially, but got the same result as you did.

I dont think so that using Segment tree will result in TLE because nlogn solution will run well within the time limit and as there are T test cases so it will be T*Nlog(N) , even then also it ainâ€™t a problem and should work . Many other contestants implemented SET or Priority Queue technique but then also the time complexity comes out to be NlogN which is equivalent to Segment tree . So it should run well within the limit .

//