Submission #1115353

#TimeUsernameProblemLanguageResultExecution timeMemory
1115353KK_1729Schools (IZhO13_school)C++17
15 / 100
653 ms90144 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}

void solve(){
    int n, m, s; cin >> n >> m >> s;
    vector<vector<int>> music;
    vector<vector<int>> sports;
    
    vector<vector<int>> cities;
    FOR(i,0,n){

        int a, b; cin >> a >> b;
        music.pb({a, b, i});
        sports.pb({b, a, i});
        cities.pb({a, b});
    }
    sort(all(music));
    reverse(all(music));
    sort(all(sports));
    reverse(all(sports));

    set<int> cm;
    set<int> cs;
    int ans = 0;
    FOR(i,0,m){
        cm.insert(music[i][2]);
        ans += music[i][0];
    }
    FOR(i,0,s){
        cs.insert(sports[i][2]);
        ans += sports[i][0];
    }

    vector<int> common;
    multiset<vector<int>, greater<vector<int>>> not_taken_m;
    multiset<vector<int>, greater<vector<int>>> not_taken_s;
    FOR(i,0,n){
        if (cm.count(i) && cs.count(i)) common.pb(i);
        if (!cm.count(i) && !cs.count(i)){
            not_taken_m.insert(cities[i]);
            not_taken_s.insert({cities[i][1], cities[i][0]});
        }
    }
    // cout << ans << endl;
    for (auto item: common){
        if (not_taken_m.size()){
            auto x = not_taken_m.begin();
            // printVector(*x);
            if (not_taken_s.size()){
                auto y = not_taken_s.begin();
                

                if ((*x)[0]-cities[item][0] > (*y)[0]-cities[item][1]){
                    ans += (*x)[0]-cities[item][0];
                    not_taken_m.erase(x);
                }else{
                    ans += (*y)[0]-cities[item][1];
                    not_taken_s.erase(y);
                }
                continue;
            }
            ans += (*x)[0]-cities[item][0];
            not_taken_m.erase(x);
        }else{
            auto y = not_taken_s.begin();
            ans += (*y)[0]-cities[item][1];
            not_taken_s.erase(y);
        }
    }


    cout << ans << endl;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1; // cin >> t;
    while (t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...