Editorial for Yet Another Contest 2 P6 - Travel Budget

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

Clearly, it is optimal to always go east. We can use dynamic programming to solve this problem.

Define as the minimum cost to reach the -th town from the -th town, assuming that we will start by using the -th car.

Then, we can loop over all possible towns in which we will switch from the -th car to the -th car. Then, we will update as . Make sure to only consider feasible values of , where .

The base case is , and the answer to the problem is .

Time complexity:

Let's try to optimise our dp transition from before. Since for all , we do not need to consider which towns are reachable using the -th car.

Recall that .

We can rewrite this as .

If we compute our dp bottom-up, then we can optimise our transition using the convex hull trick. This is because we are essentially keeping a set of lines in the form , and to calculate , we find the line in our set which minimises the value of . Once we compute , we add the line into our set.

Note that we are not guaranteed that the gradients of the lines we insert are in non-increasing order. Thus, we require the dynamic implementation of the convex hull trick.

Alternatively, we can optimise our dp using the same method using a Li Chao Tree.

Time complexity: