ABC 331

Table of Contents

E - Set Meal

https://atcoder.jp/contests/abc331/tasks/abc331_e

解説 AC

2025/2/23 retry

副菜を降順にソートしておく。主菜を固定したときに選べる副菜のうち一番高いものを採用する。全ての主菜に対して同じことをしてそのうちの最大を出力。 選ぶ必要のない副菜の検索を飛ばすことで $N+L$ 回程度の比較しかされないので十分早い。

void solve() {
    ll n, m, l;
    cin >> n >> m >> l;
    vll a(n), b(m), c(l), d(l);
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];
    rep(i, l) {
        cin >> c[i] >> d[i];
        c[i]--, d[i]--;
    }

    vector<pair<ll, int>> B;
    rep(i, m) B.push_back({b[i], i});

    sort(rall(B));

    set<pair<int, int>> ban;
    rep(i, l) ban.insert({c[i], d[i]});

    ll ans = 0;
    rep(i, n) {
        rep(j, m) {
            if (!ban.count({i, B[j].second})) {
                chmax(ans, a[i] + B[j].first);
                break;
            }
        }
    }
    cout << ans << endl;
}