Submission #16937

#	Time	Username	Problem	Language	Result	Execution time	Memory
16937		erdemkiraz	Schools (IZhO13_school)	C++98	100 / 100	365 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; 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;
    }

    if(!s) {
        printf("%lld\n", add - s2.begin() -> first);
        return 0;
    }

    if(!m) {
        printf("%lld\n", sum);
        return 0;
    }

    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);
        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: 100 / 100