Submission #1302163

#TimeUsernameProblemLanguageResultExecution timeMemory
1302163domiSchools (IZhO13_school)C++20
95 / 100
64 ms11520 KiB
#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "Yes" << endl; return; }
#define NO { cout << "No" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 3e5;

using namespace std;

pii a[NMAX + 5];
int pre[NMAX + 5], suf[NMAX + 5], n, m, s;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> s;

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

    sort(a + 1, a + n + 1, [](const pii& a, const pii& b) {
        return (a.fi - a.se) > (b.fi - b.se);
    });

    priority_queue<int, vector<int>, greater<int>>pq_st;
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (pq_st.size() == m && a[i].fi > pq_st.top()) {
            sum += (a[i].fi - pq_st.top());
            pq_st.pop();
            pq_st.push(a[i].fi);
        }

        if (pq_st.size() < m) {
            sum += a[i].fi;
            pq_st.push(a[i].fi);
        }

        pre[i] = sum;
    }

    priority_queue<int, vector<int>, greater<int>>pq_dr;
    sum = 0;
    for (int i = n; i >= 1; --i) {
        if (pq_dr.size() == s && a[i].se > pq_dr.top()) {
            sum += (a[i].se - pq_dr.top());
            pq_dr.pop();
            pq_dr.push(a[i].se);
        }

        if (pq_dr.size() < s) {
            sum += a[i].se;
            pq_dr.push(a[i].se);
        }

        suf[i] = sum;
    }

    int ans = INT_MIN;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, pre[i] + suf[i + 1]);

    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...