Submission #1096971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096971		codexistent	Schools (IZhO13_school)	C++14	100 / 100	139 ms	12760 KiB

school

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 300005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)

ll n, t[2], pfx[MAXN], r = 0;
vector<array<ll, 2>> v(MAXN);

int main(){
    cin >> n >> t[0] >> t[1];
    FOR(i, 1, n) cin >> v[i][0] >> v[i][1];

    sort(begin(v) + 1, begin(v) + 1 + n, [&](const auto &a, const auto &b) {
        return a[0] - a[1] > b[0] - b[1];
    });

    priority_queue<ll> pq;
    pfx[0] = 0;
    FOR(i, 1, n){
        pfx[i] = pfx[i - 1];
        pfx[i] += v[i][0], pq.push(-v[i][0]);
        while((ll)pq.size() > t[0]) pfx[i] += pq.top(), pq.pop();
    }

    priority_queue<ll>().swap(pq);
    ll sfx = 0;
    for(ll i = n + 1; i >= 1; i--){
        if(i <= n){
            sfx += v[i][1];
            pq.push(-v[i][1]);
            while((ll)pq.size() > t[1]) sfx += pq.top(), pq.pop();
        }

        if((ll)pq.size() == t[1] && i - 1 >= t[0]) r = max(r, sfx + pfx[i - 1]);
    }

    cout << r << endl;
}

• Subtask 1: 100 / 100