Consider minimizing the travel distance instead of the cost.

Each time you reach a station, you may fully refuel there. Therefore, the state of the car can be represented by the remaining amount of fuel that cannot be refueled at the current station. Let’s denote this value as \(x\).

It is inefficient to change direction at a place without a station, so let’s focus on the movement from one station to another. When moving to a station at a distance \(a\), the value of \(x\) changes as follows. Hereafter, we treat coordinate \(0\) as station \(0\) and coordinate \(L\) as station \(N+1\). It is fine if either type of fuel is available at these stations.

• When the fuel type at the current station and the destination station is the same: \(x \to x-\max(a-C,0)\).
• When the fuel type at the current station and the destination station is different: \(x \to \min(x+C-a,C)\).

The first pattern and the case of \(a \geq C\) in the second pattern can be summarized as \(x \to x-v\). We will call this movement a “\(-v\)” move.

The case of \(a < C\) in the second pattern can be written as \(x \to \min(x+v,C)\). We will call this a “\(+v\)” move.

If \(x\) becomes negative, it means the movement has failed.

The final goal is to reach coordinate \(L\) without \(x\) becoming negative. Sometimes, moving only to the right is not enough, and you need to return to refuel.

Here, the following proposition holds:

• Proposition: There exists an optimal solution where all leftward movements are \(+\) moves, and immediately after moving left, the car always moves right.

Proof: Among the \(+\) moves, take the one with the maximum \(+v\). Suppose this is between station \(i\) and \(i+1\). Assume that there is a move from station \(i\) to \(i-1\) in some solution. It is never disadvantageous to replace the sequence of operations where the car moves left from \(i\) and returns to \(i\) with round trips between stations \(i\) and \(i+1\). Specifically, the number of round trips should be half the number of \(+\) moves (which is always even). Thus, we may assume the operation \(i \to i-1\) does not exist. Similarly, we may assume the operation \(i+2 \to i+1\) does not exist. Therefore, the original problem can be decomposed into moving from station \(0\) to \(i\) and from station \(i+1\) to \(N+1\). By applying the same argument to each part, the proposition is shown.

Therefore, instead of leftward movements, we can consider refueling by making round trips between adjacent stations. Based on this observation, consider the following DP:

• \(dp[i][j]=\) the minimum distance of round trips made so far when at station \(i\) with \(x=j\).

Consider the transition \(dp[i] \to dp[i+1]\). When the move from station \(i \to i+1\) is a \(-v\) move, the transition is simply \(dp[i+1][j-v]=dp[i][j]\). Of course, discard parts where \(j-v<0\).

If it is a \(+v\) move, first perform the transition \(dp[i+1][\min(j+v,C)]=dp[i][j]\). Then, perform the transition \(\operatorname{changemin}(dp[i+1][\min(j+2v,C)],dp[i+1][j]+2(C-v))\). This transition corresponds to the operation of refueling \(2v\) liters of fuel at a cost of \(2(C-v)\) per round trip.

Here, we cap \(j\) at \(C\) while transitioning, but instead we can discard \(j\) that exceeds \(C\) to efficiently simulate this DP. We call the pairs \((j,dp[i][j])\) that are maximal in \(j\) and minimal in \(dp[i][j]\) as representative points of \(dp[i]\). By focusing on the differences between adjacent representative points, we see that they are “sorted.” That is, when viewed in ascending order of \(j\), the rate of increase in \(j\) gradually decreases, while the rate of increase in \(dp[i][j]\) gradually increases.

The set of representative points can be represented by \(O(N)\) arithmetic sequences. By managing this with a deque, the DP can be performed in \(O(N)\) time overall.

How should we handle the operation of setting \(j\) to \(C\) when it exceeds \(C\)? This can be done by independently solving the problem where you start with a full tank at station \(i+1\).

In summary, the overall solution is as follows:

• Prepare \(A=(0,\infty,\cdots,\infty)\).
• For \(i=0,1,2,\cdots\), perform the following operations:
  • Consider the problem starting with a full tank at station \(i\) with the current cost \(A_i\). Only keep states where \(j \leq C\). When \(j > C\), perform \(\operatorname{changemin}(A_{hoge},fuga)\).

By performing the DP as above for all \(i\), we obtain a solution with a total time complexity of \(O(N^2)\).

Sample Implementation