## Editorial for Yet Another Contest 2 P6 - Travel Budget

**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:

#### Subtask 1

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:**

#### Subtask 2

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:**

#### Subtask 3

Observe that the restriction on the maximum distance that a car can travel means that when calculating , we can only consider a contiguous range of possible lines. This range can be easily found using a binary search.

To determine the minimum of any given range of lines, we can create a segment tree, where each node stores its own convex hull trick data structure or Li Chao Tree.

**Time complexity:**

## Comments