Submission #1136253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136253		Anphat	Schools (IZhO13_school)	C++20	100 / 100	76 ms	7872 KiB

school

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

#define ll long long
#define f first
#define s second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define uni(a) sort(all(a)), (a).resize(unique(all(a)) - (a).begin())

typedef pair <int, int> ii;

const int N = 3e5 + 1;

priority_queue <int, vector <int>, greater <int>> pq;
int n, m, s;
ll pre[N], suf[N], ans, cur;
ii a[N];

void solve() {
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].f >> a[i].s;
    }
    
    sort(a + 1, a + n + 1, [&](ii a, ii b){return a.f - a.s > b.f - b.s;});
    
    for (int i = 1; i <= n; i++) {
        cur += a[i].f; pq.push(a[i].f);
        while (sz(pq) > m) {
            int top = pq.top(); pq.pop();
            cur -= top;
        }
        pre[i] = max(pre[i], cur);
    }
    
    while (sz(pq)) pq.pop();
    cur = 0;
    
    for (int i = n; i >= 1; i--) {
        cur += a[i].s; pq.push(a[i].s);
        while (sz(pq) > s) {
            int top = pq.top(); pq.pop();
            cur -= top;
        }
        suf[i] = max(suf[i + 1], cur);
    }
    
    for (int i = m; i + s <= n; i++) {
        ans = max(ans, pre[i] + suf[i + 1]);
    }
    
    cout << ans << '\n';
}

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

    // freopen("a.inp", "r", stdin);
    // freopen("a.out", "w", stdout);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

• Subtask 1: 100 / 100