제출 #1149031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149031		uasdfae	학교 설립 (IZhO13_school)	C++17	100 / 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 c, ii b) { return c.fi - c.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 + 1; i++) {
        res = max(res, pref[i] + suf[i + 1]);
    }
    cout << res;
}

• Subtask 1: 100 / 100