Submission #176003

#	Time	Username	Problem	Language	Result	Execution time	Memory
176003		emil_physmath	Schools (IZhO13_school)	C++17	100 / 100	274 ms	17272 KiB

school

// #define DEBUG
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long llong;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, aNum, bNum;
    cin >> n >> aNum >> bNum;
    struct City
    {
        int a, b;
    };
    vector<City> cities(n);
    for (int i = 0; i < n; ++i)
        cin >> cities[i].a >> cities[i].b;
    if (!aNum)
    {
        sort(cities.begin(), cities.end(), [](const City& lhs, const City& rhs) {
             return lhs.b > rhs.b;
        });
        long long ans = 0;
        for (int i = 0; i < bNum; ++i)
            ans += cities[i].b;
        cout << ans;
        exit(0);
    }
    if (!bNum)
    {
        sort(cities.begin(), cities.end(), [](const City& lhs, const City& rhs) {
             return lhs.a > rhs.a;
        });
        long long ans = 0;
        for (int i = 0; i < aNum; ++i)
            ans += cities[i].a;
        cout << ans;
        exit(0);
    }
    sort(cities.begin(), cities.end(), [](const City& lhs, const City& rhs) {
         return lhs.a - lhs.b > rhs.a - rhs.b;
    });
    vector<long long> pref(n, -30'000'000'000LL), suff(n, -30'000'000'000LL);
    multiset<int> a;
    long long sum = 0;
    for (int i = 0; i < aNum; ++i)
    {
        a.insert(cities[i].a);
        sum += cities[i].a;
    }
    pref[aNum - 1] = sum;
    for (int i = aNum; i < n; ++i)
    {
        sum += cities[i].a;
        a.insert(cities[i].a);
        sum -= *a.begin();
        a.erase(a.begin());
        pref[i] = sum;
    }
    sum = 0;
    multiset<int> b;
    for (int i = 1; i <= bNum; ++i)
    {
        b.insert(cities[n - i].b);
        sum += cities[n - i].b;
    }
    suff[n - bNum] = sum;
    for (int i = bNum + 1; i <= n; ++i)
    {
        sum += cities[n - i].b;
        b.insert(cities[n - i].b);
        sum -= *b.begin();
        b.erase(b.begin());
        suff[n - i] = sum;
    }
    long long ans = 0;
    for (int i = 0; i + 1 < n; ++i)
        ans = max(ans, pref[i] + suff[i + 1]);
    cout << ans;
}

• Subtask 1: 100 / 100