初めに

atcoder.jp 解けなかったので

敗因

実はけっこう前から温めてた問題. 最初は精選100 + 50 問で, RMQ の練習問題としておいてあったのを見て.

普通に考察すると何回魔法を使うかで場合分けして最小値をうまくとるみたいな噓貪欲をはやして 9 WA (In 21 cases)...(ちなみにどういうケースで落ちてるかまだ分かっていません...) atcoder.jp

魔法を使う回数を固定する( $k$ とする)と, スライム $i$ を捕まえるためには, スライム $i, i-1, \ldots , i-k$ を捕まえればよい.

(これはスライム $i$ 以外のスライムと干渉しない. (Editorial PDF の図みたいに, 魔法を使うところにスライムを捕まえるイベントを適切位置に挿入していくようにすれば構築できるので.))

よって, $ans_k = k \cdot x + \sum_{i=1}^N min(A_i, A_{i-1}, \ldots , A_{i-k})$ となるので RMQ を用いると $O( N^2 log N )$ で解けた.

( $min(A_i, A_{i-1}, \ldots , A_{i-k})$ は累積minみたいな感じで $O(1)$ で計算することができるので $log$ を落すこともできる(公式 Editorial の解法))

魔法の使う回数固定は合ってただけに悔しい.

(魔法操作に購入操作を挿入するという考え(→各スライムの購入は独立という考え)ができませんでした...)

あと RMQ は想定解じゃないのか... (そもそも静的区間minだから線形RMQすれば $O(N^2)$ か)