Submission #1149030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149030		uasdfae	Schools (IZhO13_school)	C++17	20 / 100	77 ms	11576 KiB

school

#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef pair<ll, ll> ii;
#define fi first
#define se second
#define mask(i) (1LL << (i))


const int N = 3e5 + 5;
const ll inf = 1e17;

int k, n, m;
ii a[N];
ll pref[N], suf[N];

bool cmp(ii a, ii b) { return a.fi - a.se > b.fi - b.se; }

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);


    cin >> k >> n >> m;
    for (int i = 1; i <= k; i++) cin >> a[i].fi >> a[i].se;

    sort(a + 1, a + k + 1, cmp);

    priority_queue<ll, vector<ll>, greater<ll>> q1;
    ll sum = 0;
    for (int i = 1; i <= k; i++) {
        sum += a[i].fi; q1.push(a[i].fi);
        while (q1.size() > n) {
            sum -= q1.top(); q1.pop();
        }
        pref[i] = sum;
    }

    priority_queue<ll, vector<ll>, greater<ll>> q2;
    sum = 0;
    for (int i = k; i >= 1; i --) {
        sum += a[i].se; q2.push(a[i].se);
        while (q2.size() > m) {
            sum -= q2.top(); q2.pop();
        }
        suf[i] = max(sum, suf[i + 1]);
    }

    ll res = 0;
    for (int i = n; i <= k - m; i++) {
        res = max(res, pref[i] + suf[i]);
    }
    cout << res;
}

• Subtask 1: 20 / 100