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; }