Summer Vacation [AtCoder Beginner Contest 137 D]

https://atcoder.jp/contests/abc137/tasks/abc137_d

解説

https://atcoder.jp/contests/abc137/submissions/6894414

後ろから決めていこう。
最終日に選ぶことができるのは、A[i]=1のアルバイトだけ。
最終-1日に選ぶことができるのは、A[i]=1,2のアルバイト。
後ろから決めていくと候補者がどんどん増えていく感じになる。
どんどん増えていく候補者の中から、最も報酬が高い人を選んでいく貪欲をすれば答えが得られる。
貪欲解を出すのは怖いのだが、一般のdpで解けそうにない+400点ということから貪欲解が来そうな感じはする。

int N, M, A[101010], B[101010];
vector<int> Q[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i] >> B[i];
    rep(i, 0, N) Q[A[i]].push_back(B[i]);

    priority_queue<int> que;
    int ans = 0;
    rep(m, 1, M + 1) {
        fore(b, Q[m]) que.push(b);
        if (!que.empty()) {
            ans += que.top();
            que.pop();
        }
    }

    cout << ans << endl;
}