Codeforces #413 C: Fountains

解説付きコード

/*
解候補は4種類ある。
何も買わない
コインとダイヤモンドでそれぞれ1個ずつ噴水を買う
コインで2個噴水を買う
ダイヤモンドで2個噴水を買う

前二者は自明

後二者について
噴水をコインで2個買うとする
安い方の必要なコイン数を固定すると、
使える残りのコイン数が決まる。
そのコインの数以下で変える最大の美しさを持つ噴水も確定する。
よって、安い方の噴水を昇順で固定して、
それより安い噴水と高くて買えない噴水を候補から外す。
*/

/*
コインだけ、もしくはダイヤモンドだけで2個の噴水を買いたい
*/
int f(vector<pii> &a, int m) {
    // price_beauty, beauty_price
    // 前者は値段で、後者は美しさで
    // 最大値、最小値を取得できる
    multiset<pii> p_b, b_p;
    auto g = [&](int p, int b) {
        // multisetの削除はイテレータを使うこと
        // そうでないと重複要素をすべて削除してしまう。
        p_b.erase(p_b.find(mp(p, b)));
        b_p.erase(b_p.find(mp(b, p)));
    };
    rep(i, sz(a)) {
        p_b.insert(a[i]);
        b_p.insert(mp(a[i].second,a[i].first));
    }
    int res = 0;
    while (sz(p_b) > 1) {
        int p1, b1;
        // 安い方の噴水の値段,美しさ
        tie(p1, b1) = *p_b.begin();
        if (p1 > m)break;
        // この噴水を解候補から削除
        g(p1, b1);
        // あとlimコインだけ使える
        int lim = m - p1;
        // 高すぎる噴水を削除
        while (sz(p_b) && p_b.rbegin()->first > lim) {
            int p, b;
            tie(p, b) = *p_b.rbegin();
            g(p, b);
        }
        if (sz(p_b) == 0)break;
        // 買える噴水のうち最も美しいもの
        int b2 = b_p.rbegin()->first;
        smax(res, b1 + b2);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, C, D;
    cin >> N >> C >> D;
    vector<pii> cs, ds;
    int mac = 0, mad = 0;
    rep(i, N) {
        int b, p;
        char c;
        cin >> b >> p >> c;
        if (c == 'C') {
            cs.emplace_back(p, b);
            if (p <= C) {
                // ここをmac=bとしてしまった
                smax(mac, b);
            }
        }
        if (c == 'D') {
            ds.emplace_back(p, b);
            if (p <= D) {
                // ここをmad=bとしてしまった
                smax(mad, b);
            }
        }
    }

    int ans = 0; // 何も買わない場合がある
    if (mac > 0 && mad > 0)ans = mac + mad; // コインとダイヤモンドを両方使う場合
    // コインだけ、もしくはダイヤモンドだけ
    smax(ans, max(f(cs, C), f(ds, D)));
    cout << ans << endl;
}