제출 #16934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16934		erdemkiraz	학교 설립 (IZhO13_school)	C++98	80 / 100	337 ms	18060 KiB

school

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 3e5 + 5;

int n, m, s;
ii a[N];

int main() {

    scanf("%d %d %d", &n, &m, &s);

    for(int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i].second, &a[i].first);
    }

    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);

    for(int i = 1; i <= n; i++)
        swap(a[i].first, a[i].second);

    ll sum = 0, add = 0, ans = 0;

    set < ii > s1, s2;

    for(int i = 1; i < s; i++) {
        sum += a[i].second;
        s1.insert(ii(a[i].first - a[i].second, i));
    }

    for(int i = s + 1; i <= n; i++) {
        s2.insert(ii(a[i].first, i));
    }

    while(s2.size() > m + 1) {
        s2.erase(*s2.begin());
    }

    foreach(it, s2) {
        add += it -> first;
    }

    for(int i = s; ; i++) {
        if(!s2.size())
            break;
        if(s2.find(ii(a[i].first, i)) == s2.end()) {
            add -= s2.begin() -> first;
            s2.erase(s2.begin());
        }
        else {
            add -= a[i].first;
            s2.erase(ii(a[i].first, i));
        }
        ll res = sum + add + a[i].second;
        ans = max(ans, res);
        //printf("i = %d res = %lld ans = %lld\n", i, res, ans);
        //printf("sum = %d add = %d\n", sum, add);
        ii best = s1.size() ? *s1.rbegin() : ii(0, 0);
        if(!s1.size() or a[i].first > a[i].second + best.first) {
            sum += a[i].first;
        }
        else {
            sum += a[i].second + best.first;
            s1.erase(*s1.rbegin());
            s1.insert(ii(a[i].first - a[i].second, i));
        }
    }

    printf("%lld\n", ans);

    return 0;

}

• Subtask 1: 80 / 100