Ball [RUPC2018 Day2 C]

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day2/2751424

まず個数Mは無視して、価値を最大化するようにボールを取ってみよう。
すると、各色について価値の大きい順に取れるだけボールを取れば最適となる。
元の問題で使われるボールはここで使われたボールから選ばれる。
あとは、このボールを全て集めて価値の大きい順に最大M個ボールを取れば答えとなる。

int N, M, C, l[101010], c[101010], w[101010];
vector<int> v[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> C;
    rep(i, 0, C) cin >> l[i];
    rep(i, 0, N) {
        cin >> c[i] >> w[i];
        c[i]--;
        v[c[i]].push_back(w[i]);
    }
    vector<int> w;
    rep(i, 0, C) {
        sort(all(v[i]), greater<int>());
        int n = min(l[i], (int)v[i].size());
        rep(j, 0, n) w.push_back(v[i][j]);
    }
    sort(all(w), greater<int>());

    int n = min(M, (int)w.size());
    ll ans = 0;
    rep(i, 0, n) ans += w[i];
    cout << ans << endl;
}