ABC #116 D
まずはおいしさの大きい方から \(K\) 個取る. おいしさ基礎ポイントはこれ以上は大きくできないので, 満足ポイントを増やすためには種類ボーナスポイントを増やすしかない.
種類ボーナスポイントを1増やすには, 2個以上食べてるネタのうち最も小さいおいしさの寿司を外し, 残りのうちからまだ食べていないネタのうち最も大きいおいしさの寿司を入れるのが最適となる.
よって, 以下の方針で実装する.
- 寿司はおいしさの降順にソートしておく.
- これを上位 \(K\) 個と残りに分ける. 上位 \(K\) 個についてはネタごとに個数を計算しておき, 満足ポイントも計算しておく.
- 上位 \(K\) 個を下から見ていき, 2個以上あるネタのうち最も小さいおいしさの寿司を選び, 残りは上から見ていき, 使われていないネタのうち最も大きいおいしさの寿司を選ぶ. このときの満足ポイントは差分で求める.
- 以下これを繰り返す. ただし上位 \(K\) 個を下から見ていくとき, 前回外した寿司より上しか見なくてもいい. また, 残りを上から見ていくとき, 前回入れた寿司より下の寿司しか見なくてもいい.
- 外す寿司または入れる寿司がなくなったら終了である.