제출 #949254

#제출 시각아이디문제언어결과실행 시간메모리
949254TrinhKhanhDung학교 설립 (IZhO13_school)C++14
100 / 100
97 ms12772 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("TAMCAM.inp", "r", stdin);
    // freopen("TAMCAM.out", "w", stdout);

    int k, n, m;
    cin >> k >> n >> m;

    vector<pair<int, int>> a(k);
    for(pair<int, int> &o: a){
        cin >> o.first >> o.second;
    }

    sort(a.begin(), a.end(), [&](pair<int, int> a, pair<int, int> b){
        return a.second - a.first < b.second - b.first;
    });

    vector<ll> L(k + 3, 0), R(k + 3, 0);

    {
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        ll cur = 0;
        for(int i=1; i<=k; i++){
            cur += 1LL * a[i - 1].first;
            pq.push(a[i - 1].first);

            if((int)pq.size() > n){
                cur -= pq.top();
                pq.pop();
            }

            L[i] = cur;
        }
    }

    {
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        ll cur = 0;
        for(int i=k; i>=1; i--){
            cur += 1LL * a[i - 1].second;
            pq.push(a[i - 1].second);

            if((int)pq.size() > m){
                cur -= pq.top();
                pq.pop();
            }

            R[i] = cur;
        }
    }

    ll ans = 0;
    for(int i=n; i<=k-m; i++){
        ans = max(ans, L[i] + R[i + 1]);
    }

    cout << ans << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...