コストの代わりに移動距離を最小化することを考えます．

ステーションに到達する度にそこで燃料を満タンにして構いません． よって車の状態は，今いるステーションで補給できない燃料の残量で表すことができます． この値を \(x\) で表すことにします．

ステーションのない場所で方向転換しても損するばかりなので，ステーションから別のステーションへの移動に注目します． 距離 \(a\) 離れたステーションに移動するとき，\(x\) の値は以下のように変化します． なお，以降は座標 \(0\) をステーション \(0\)，座標 \(L\) をステーション \(N+1\) として扱います．これらのステーションで補給できる燃料はどちらであってもよいです．

• 今いるステーションと移動先のステーションの燃料の種類が同じ時 : \(x \to x-\max(a-C,0)\) と変化する．

• 今いるステーションと移動先のステーションの燃料の種類が違う時 : \(x \to \min(x+C-a,C)\) と変化する．

\(1\) つめのパターンと，\(2\) つめのパターンの \(a \geq C\) のケースは，\(x \to x-v\) という形でまとめられます． この移動を \(-v\) 移動と呼ぶことにします．

\(2\) つめのパターンの \(a <C\) のケースは \(x \to \min(x+v,C)\) という形でかけます．これを \(+v\) 移動と呼ぶことにします．

もし \(x\) が負の値になったら，それは移動に失敗したことを意味します．

最終的な目標は，\(x\) が負にならないように座標 \(L\) まで到達することです． 車が右に進むだけでは目標達成できないこともあり，その場合は左に戻って燃料を補給する必要があります．

ここで以下の命題が成り立ちます．

• 命題: ある最適解が存在して，そこでは左に戻る移動は必ず \(+\) 移動で，さらに左に戻った直後の移動では必ず右に進む．

証明: \(+\) 移動の中で \(+v\) が最大のものを取ってくる． これがステーション \(i\) と \(i+1\) の間だとする． ある解において，ステーション \(i \to i-1\) という移動があったとする．\(i\) から左に動いたあと再び \(i\) に戻ってくるという一連の操作をステーション \(i\) と \(i+1\) の往復に置き換えることで絶対に損しない． 具体的には，\(i \to i\) の一連の操作内の \(+\) 移動の回数 (これは必ず偶数) \(/2\) 回往復すればよい． よって，\(i \to i-1\) という操作は存在しないとしてよい． 同様に，\(i+2 \to i+1\) という操作も存在しないものとしてよい． すると元の問題は，ステーション \(0 \to i\) と ステーション \(i+1 \to N+1\) に分解できる．それぞれで今と同じ議論をすることで，命題が示される．

よって，左に戻る操作ではなく，隣接ステーション間で往復して補給するという操作を考えればよくなります． この考察をもとに次のような DP を考えます．

• \(dp[i][j]=\) ステーション \(i\) において \(x=j\) であるときの，今まで行った往復移動の距離の最小値

\(dp[i] \to dp[i+1]\) の遷移を考えます． ステーション \(i \to i+1\) が \(-v\) 移動のときは，\(dp[i+1][j-v]=dp[i][j]\) という遷移を行うだけです．もちろん \(j-v<0\) の部分は捨てます．

\(+v\) 移動だった場合は，まず \(dp[i+1][\min(j+v,C)]=dp[i][j]\) という遷移を行います． その後，\(\operatorname{changemin}(dp[i+1][\min(j+2v,C)],dp[i+1][j]+2(C-v))\) という遷移を行います． この遷移は，\(1\) 往復あたりコスト \(2(C-v)\) で \(2v\) リットルの燃料を補給するという操作に対応します．

遷移の際に \(j\) を \(C\) で上から抑えていますが，その代わりに \(j\) が \(C\) を超えたら捨てるという風に変えると，この DP は高速にシミュレートできます． ペア \((j,dp[i][j])\) のうち，\(j\) に関して極大かつ \(dp[i][j]\) に関して極小なものを，\(dp[i]\) の代表点と呼ぶことにします． 隣り合う代表点の差分に注目すると，これは”ソートされている”ということがわかります． つまり，代表点を \(j\) の昇順に見たとき，\(j\) が増加する速度はだんだんと小さくなり，逆に \(dp[i][j]\) が増加する速度はだんだんと大きくなります．

代表点の集合は \(O(N)\) 個の等差数列で表現することができます． これを deque で管理することで，DP が全体 \(O(N)\) で行えます．

では \(j\) が \(C\) を超えたものを \(C\) にするという操作にはどう対処すればよいでしょうか． これは単に，ステーション \(i+1\) で満タンの状態からスタートするという問題を独立に解けばよいです．

まとめると，解法の全容は以下のようになります．

• \(A=(0,\infty,\cdots,\infty)\) を用意する．
• \(i=0,1,2,\cdots\) について以下の操作を行う．
  • ステーション \(i\) で燃料が満タンであり，現在のコストが \(A_i\) の状態からスタートする問題を考える．\(j\leq C\) の状態だけを保持する．\(j>C\) になったら，そのタイミングで \(\operatorname{changemin}(A_{hoge},fuga)\) を行う．

すべての \(i\) に対し，上で述べた方法で DP を行うことで，全体 \(O(N^2)\) 時間の解法が得られます．

回答例