제출 #176001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
176001		emil_physmath	학교 설립 (IZhO13_school)	C++17	95 / 100	269 ms	20828 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;
    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 << endl;
}

• Subtask 1: 95 / 100