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