https://atcoder.jp/contests/abc137/submissions/15521766
- x日後を前から見るのでなく、後ろから見たほうが条件が狭くなる
- （後ろから）x日以内に報酬を貰えるバイトのうち最大を貪欲に選べばok
x日後を前から考えるより後ろから考えたほうが条件が狭くなるので、後ろから見て考えるテクニックを使う。報酬を貰えるのは数日後だが、バイト自体は1日で終わるので、（後ろから）x日以内に報酬を貰えるバイトのうち最大報酬のバイトを貪欲に採用していけば良い。
ただし、制約から各x日にすべきバイトを以下で選ばなければならないので、priority_queueを使って最大の報酬を貰えるバイトを取り出す。このとき、入力を受け取った時点でx日目に選べるバイトqを二次元配列jobs[x][q]で受け取るようにしておくとpriority_queueにpushする実装が楽になる。全体計算量は
になる。
