https://atcoder.jp/contests/abc137/tasks/abc137_d
後ろから貪欲法で解ける気がする。 M-1 日目を考えると、 残っている仕事のうち、 Ai=1 を満たす仕事で報酬 Bi が最大となるものを請けるとして良いことがわかる。
必要であれば受けた仕事の順番を入れ替えて、 M-1 日目にする仕事は、全ての N 件の日雇いバイトの中で Ai=1 を満たし報酬 Bi が最大となる仕事である、とできる。
次に M-2 日目を考えると、できる仕事は Ai=1,2 である仕事。Ai=1,Bi が最大となる仕事は最終日にやることが決まっているので、 M-1 日目と同様の考察により、それを除いた仕事のうち報酬が最大となるものを働けば良い。
以下繰り返す。