AGC024 B - Colorful Slimes

問題
提出コード

解法

スライムを好きなタイミングで捕まえることができ、捕まえる、魔法を唱える、捕まえる魔法を唱える…といったような順番で操作を行うことができます。ので、魔法を唱えるを唱える回数をまずは固定してしまって、捕まえるスライムの種類を決めてから、最後にを追加します。
これをについて全探索して最小値を求めることで答えを求めていきます。
回魔法を唱えることにすると、回のうち好きな回数変色ができます。
ということで、魔法を唱える回数が決まってしまっているので、番目のスライムを入手したいとき、～のスライムのうち一番入手時間が短いものを選んでくると、番目のスライムを入手するために必要な時間を最小にすることができます。
区間についての最小値を求めたいので、RMQを使ってごり押しをします。
が負になる場合を考慮するために、RMQは要素数をにし、～を2つ並べます。すると、は負になることがない(魔法を唱える回数がより大きくなったときに答えとなることは絶対にありません)ので、配列外を参照することはなくなります。
ということで、あとは全てのについて、区間の最小値をRMQで求めて加算していき、最後にを追加すれば回魔法を唱える場合の最小値になります。
これをについて全探索することで、答えが求まります。