colorful slimes - agc 004 b

リンク1は間違えたコード。
この問題のポイントは、部分最適が全体最適にならないところ。
4 1
5 3 2 1
という例を考える。

部分最適にするなら
(1 + 1) + 3 + 2 + 1 = 8
となる。
全体最適にするなら
1 * 4 + 1 * 3 = 7
となる。
1を4つ作って3回魔法を使う。
移動コスト3 / (1 + 2 + 3) = 0.5で、
1 + 0.5 * 3, 1 + 0.5 * 2, 1 + 0.5, 1
というコストになる。

リンク2のソースコードはリンク1のソースコードでwaになるケースを作るもの。

他のケースも考える。
4 4
4 5 1 5
k = 1のとき解が得られる。
4 * 1 + 4 + 4 + 1 + 1 = 14

リンク1、Submission #6749113 - AtCoder Grand Contest 004
リンク2、https://ideone.com/j5hy3U