ferinの競プロ帳

競プロについてのメモ

第3回 ドワンゴからの挑戦状 予選 D - ネタだけ食べたい寿司

dwacon2017-prelims.contest.atcoder.jp

n<=mであれば全ての寿司をネタだけ食べればいいのでm>nのときについて考える。
i番目までの寿司を食べるとすると、i番目をネタだけ食べ、1からi-1番目の中でネタだけ食べた時の幸福度の上昇が大きいものm-1個を選ぶのが最適な食べ方となる。そこで、i番目までの寿司でネタだけ食べた時の幸福度の上昇が上位m個のものを保持しておきたいのでpriority_queueを使う。