제출 #1325008

#제출 시각아이디문제언어결과실행 시간메모리
1325008ysmasyamka학교 설립 (IZhO13_school)C++20
100 / 100
103 ms12892 KiB
#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n, m, s;
	cin >> n >> m >> s;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i];

    vector<int> vt(n);
    for (int i = 0; i < n; i++)
        vt[i] = i;

    sort(vt.begin(), vt.end(), [&](int i, int j)
    {
        return (a[i] - b[i]) > (a[j] - b[j]);
    });

    vector<long long> pre(n + 1, LLONG_MIN);
    vector<long long> suf(n + 2, LLONG_MIN);

    if (m == 0)
    {
        for (int i = 0; i <= n; i++)
            pre[i] = 0;
    }

    else
    {
        priority_queue<long long, vector<long long>, greater<long long>> pq;
        long long sum = 0;
        for (int i = 1; i <= n; i++)
        {
            int id = vt[i - 1];
            pq.push(a[id]);

            sum += a[id];
            if (pq.size() > m)
            {
                sum -= pq.top();
                pq.pop();
            }

            if (pq.size() == m)
                pre[i] = sum;

            else
                pre[i] = LLONG_MIN;
        }
    }

    if (s == 0 )
    {
        for (int i = 1; i <= n + 1; i++ )
            suf[i] = 0;
    }

    else
    {
        priority_queue<long long, vector<long long>, greater<long long>> pq;
        long long sum = 0;
        for (int i = n; i >= 1; i--)
        {
            int id = vt[i - 1];
            pq.push(b[id]);

            sum += b[id];
            if (pq.size() > s)
            {
                sum -= pq.top();
                pq.pop();
            }

            if (pq.size() == s)
                suf[i] = sum;

            else
                suf[i] = LLONG_MIN;
        }
    }

    long long ans = 0;
    bool check = false;
    for (int i = 0; i <= n; i++ )
    {
        if (pre[i] > LLONG_MIN / 2 && suf[i + 1] > LLONG_MIN / 2 )
        {
            long long val = pre[i] + suf[i + 1];
            if (!check || val > ans )
            {
                ans = val;
                check = true;
            }
        }
    }

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