My solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm?

heap?:D
just use lower_bound

And, BTW, Yes there is.
At first I used Binary Search on each station but on the next station you can start with the previous index. code:


int canReach1 = A[i] + L1;
while (ind1 <= end && A[ind1] <= canReach1) ind1 ++;

i've used dp (which is easy to notice) with some optimization. suppose we have three stations

s1 s2 s3

and there exists path s1-s2 covered with l1, and path s1-s3 also covered with l1. then we can skip the analysis from s2. we can easily reduce used time if we create list of "allowed" stations to analyze (like s3)

You can keep deque (FIFO) of pairs (max_x,total_price) if using C1 on last trip, same for C2, same for C3. All three deques will be non-descending on price (and naturally ascending on coordinate). At each step pick minimum from non-empty deques (their front element) and push new advances to their end.

Edited by author 11.06.2026 06:16