[AtCoder] ABC 137 D – Summer Vacation

2019年8月24日

問題

方針

「明日できることは今日するな」ということで、締め切りから考えていきます。残り \( i \) 日あるとき、まだ請け負っていないアルバイトに対して \( A_j \leq i \) を満たすものの中で報酬が一番大きいものを選びます。これを \( i = 1 \) から \( i = M \) まで調べていきます。したがって、 \( A_j \) を昇順に整列させ、\( A_j \leq i \) を満たすアルバイトについて、優先度付きキューに \( B_j \) を格納します。そして、キューに値が存在すれば、最大の報酬を一つ加算していきます。

コード