ABC461 C - Variety

考え方

基本的には貪欲に価値が高いものを選んでいけばよい。
ただし、色を最低でも $M$ 種類選ばなければいけない点に工夫が必要となる。

まず、手作業か何かでやるなら、以下のように考えることができる。
まず、各色の中で最も価値が高いものだけ見ていき、価値が高いものから $M$ 個を採用する。
その後、まだ採用していないものだけ見ていき、価値が高いものから $K-M$ 個を採用する。
しかし、プログラムで書くと若干面倒であるため、これを少し改良する。

後半で考える $K-M$ 回を、「一度採用した色との重複が許される上限回数」と読み替える。
すると、全ての宝石を価値の高い順に見て、以下の処理をすればよい。

• まだ採用したことがない色であれば、採用する。
• もう採用したことがある色であれば、重複上限が残っているか確認して、以下に分岐。
  • 重複上限が残っていれば、採用して、重複上限を $1$ 減らす。
  • 重複上限が残っていなければ、不採用。

採用した宝石が $K$ 個になった時点で打ち切って、採用した価値の合計を答えればよい。

計算量は $O(N\log N)$ である。

入力例1での動作

入力を受け取る。

n: 5
k: 3
m: 2
(c, v): {(1, 30), (1, 40), (1, 50), (2, 10), (3, 20)}

宝石を価値の高い順に見る。
同じ色の宝石を追加で選べる回数は $K-M=1$ 回である。

$K=3$ 個の宝石を選んだので、価値 $10$、色 $2$ の宝石は見る必要がない。
答えは $110$ となる。

注意点

宝石の価値をいくつも加算すると、int 型からはみ出る。
結果用変数には long long 型を用いること。

別解

特になし。