操作列は \(i = 1, 2, \ldots, N\) に対して以下を順に繰り返すものとしてよいです。

• あなたが商人 \(i\) のいる方向へ \(1\) 移動することを \(0\) 回以上繰り返す。
• 商人 \(i\) があなたのいる方向へ \(1\) 移動することを \(0\) 回以上繰り返す。ただし、この操作は商人 \(i\) とあなたのいる座標が一致するまで繰り返す。
• 商人 \(i\) から品物 \(i\) を受け取る。

よって、計算量を無視すればまず以下のような解法で答えが求められることがわかります。

\(dp_{i, j}\) を品物 \(1, 2, \ldots, i\) を受け取り、座標 \(j\) にいる状態になるためにかかるコストの合計の最小値とする。\(j\) の範囲は \([-10^5, 10^5]\) のみを考えれば十分であり、\(dp_{i, j} = \min (dp_{i - 1, k} + C|j - k| + D|X_i - j|)\) により動的計画法による計算が行える。

この解法を高速化するために、slope trick のアイデアを用います。slope trick とは、区分線形な凸関数を傾きを適切に管理することにより関数への操作を高速化するアイデアです（本問題では関数の定義域は \(\mathbb{Z}\) (の有限部分集合) となるため、区分線形であることはあまり本質的ではありません）。

定義域を \(-10^5\) 以上 \(10^5\) 以下の整数とする関数 \(f_i\) を \(f_i(x) = dp_{i, x}\) となるようにとり、上記の dp を高速に計算することを目指します。\(f_i(x)\) に対して \(g_i(x) = \min (f_i(y) + C|x-y|)\) を満たすような関数 \(g_i\) をとり、\(f_{i + 1}(x) = g_i(x) + D|X_i - x|\) とすれば \(f_{i + 1}\) が得られます。

適切に傾きのデータを保持することで、これらの計算が高速に行えることを確認します。関数 \(f\) の情報を管理し、\(f\) が \(f_i\) や \(g_i\) に対応するようデータを変更していきます。

例えば、傾きの変化点と変化量（すなわち、\(f(x - 1) - f(x) \neq f(x) - f(x + 1)\) なるような \(x\) および \(f(x - 1) - 2f(x) + f(x + 1)\) の値）および左端の値 (すなわち \(f(-10^5)\) の値) 、左端の傾き（すなわち \(f(-10^5) - f(-10^5+1)\) ）を保持すればよいです。

まず \(g_i\) の計算ですが、これは \(f_i\) の傾きを \([-C, C]\) に制限することに対応します。すなわち、傾きが \([-C, C]\) の範囲内の部分では \(f_i\) から \(g_i\) で値は変わらず、そうでない点では値が変わらない点から傾き \(-C\) や \(C\) で関数を延長することとなります。すなわち、傾きが変化点する点を左端 / 右端からいくつか削除する（あるいは、変化量を減らす）操作ができればよいです。

\(g_i\) から \(f_{i + 1}\) を得るときには、単に点 \(X_i\) での傾きの差分が \(2D\) 増えることとなります。また、\(f(-10^5)\) の値は愚直に計算し直せます。

この計算は C++ における std::map のようなデータ構造を用いると十分高速に計算可能であり、より初等的には fenwick tree における二分探索を用いるのみで可能です。

これによりコストの合計の最小値は計算できましたが、復元についても考えなければいけません。

この復元は、\(f_i\) から \(g_i\) を得る操作における挙動を考えると、後ろから以下のように処理できることがわかります。

• 商人 \(i\) から品物を受け取った座標を \(x\) とする。
  • 点 \(x\) が \(f_i\) から \(g_i\) で値が変わっていないのであれば、商人 \(i - 1\) から品物を受け取った座標も \(x\) としてよい。
  • そうでないならば、\(x\) に最も近い \(f_i\) から \(g_i\) で値が変わっていないような点で商人 \(i - 1\) から品物を受け取ったとしてよい。

この計算には各時点で高速に各点での傾きを計算できる必要がありますが、これは前述のデータ構造に操作履歴をすべて保持しておけばよいです。例えば、商人 \(i\) に対応する操作で（std::map や fenwick tree などの）データ構造の \(j\) 番目の要素に \(k\) が足されたというようなデータを保持しておけば、復元の際は順に操作を巻き戻す（\(k\) を引く）ことにより計算が可能です。