oj.uz

Submission #1096971

# Submission time Handle Problem Language Result Execution time Memory
1096971 2024-10-05T15:21:21 Z codexistent Schools (IZhO13_school) C++14
100 / 100
 139 ms 12760 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 4 ms 5212 KB Output is correct
8 Correct 4 ms 5212 KB Output is correct
9 Correct 4 ms 5212 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 4 ms 5208 KB Output is correct
12 Correct 4 ms 5212 KB Output is correct
13 Correct 17 ms 6180 KB Output is correct
14 Correct 36 ms 6884 KB Output is correct
15 Correct 68 ms 8020 KB Output is correct
16 Correct 81 ms 10664 KB Output is correct
17 Correct 101 ms 11056 KB Output is correct
18 Correct 119 ms 11244 KB Output is correct
19 Correct 121 ms 11768 KB Output is correct
20 Correct 139 ms 12760 KB Output is correct