Subtask 1

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

Define ~dp[i]~ as the minimum cost to reach the ~N~-th town from the ~i~-th town, assuming that we will start by using the ~i~-th car.

Then, we can loop over all possible towns ~j~ in which we will switch from the ~i~-th car to the ~j~-th car. Then, we will update ~dp[i]~ as ~\min(dp[i], dp[j]+(p_j-p_i) \times c_i + d_i)~. Make sure to only consider feasible values of ~j~, where ~p_j-p_i \le s_i~.

The base case is ~dp[N] = 0~, and the answer to the problem is ~dp[1]~.

Time complexity: ~\mathcal{O}(N^2)~

Subtask 2

Let's try to optimise our dp transition from before. Since ~s_i = 10^9~ for all ~1 \le i \le N~, we do not need to consider which towns are reachable using the ~i~-th car.

Recall that ~dp[i] = \min_{j > i} (dp[j]+(p_j-p_i) \times c_i + d_i)~.

We can rewrite this as ~dp[i] = d_i - p_i \times c_i + \min_{j > i} (dp[j]+p_j \times c_i)~.

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 ~y = mx + b~, and to calculate ~dp[i]~, we find the line in our set which minimises the value of ~m \times c_i + b~. Once we compute ~dp[i]~, we add the line ~y = p_i \times x + dp[i]~ 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: ~\mathcal{O}(N \log N)~

Subtask 3

Observe that the restriction on the maximum distance that a car can travel means that when calculating ~dp[i]~, 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: ~\mathcal{O}(N \log^2 N)~