Submission #792859

#	Time	Username	Problem	Language	Result	Execution time	Memory
792859		someone	Cake 3 (JOI19_cake3)	C++14	100 / 100	1888 ms	16640 KiB

cake3

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 42, INF = 1e18 + 42;

struct Perl {
    int c, t;
};

Perl perl[N];
multiset<int> best, other;
int n, m, ans = -INF, deb = -1, fin = -1, sum = 0;

inline void add(int val) {
    sum += val;
    best.insert(val);
    if((int)best.size() == m-1) {
        sum -= *best.begin();
        other.insert(*best.begin());
        best.erase(best.begin());
    }
}

inline void del(int val) {
    auto it = other.find(val);
    if(it == other.end()) {
        sum -= val;
        it = best.find(val);
        best.erase(it);
        it = other.end();
        it--;
        sum += *it;
        best.insert(*it);
        other.erase(it);
    } else {
        other.erase(it);
    }
}

void dpr(int l, int r, int lOpt, int rOpt) {
    if(l == r) return;
    int i = ((l + r) >> 1),
        left = min(lOpt, i-m+1),
        right = min(rOpt, i-m+1);

    if(deb == -1) deb = fin = i;

    while(deb-1 > right) add(perl[--deb].c);
    while(fin+1 <= i) add(perl[fin++].c);
    while(deb <= right) del(perl[deb++].c);
    while(fin > i) del(perl[--fin].c);

    int val = sum + perl[right].c + 2 * perl[right].t, opt = right;
    for(int j = right-1; j >= left; j--) {
        add(perl[--deb].c);
        int x = sum + perl[j].c + 2 * perl[j].t;
        if(x > val) {
            val = x;
            opt = j;
        }
    }
    ans = max(ans, val + perl[i].c - 2 * perl[i].t);
    dpr(l, i, lOpt, opt);
    dpr(i+1, r, opt, rOpt);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> perl[i].c >> perl[i].t;
    sort(perl, perl + n,
    [](Perl a, Perl b) {
        return a.t < b.t;
    });

    dpr(m-1, n, 0, n-m);
    cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76