Submission #892149

#	Time	Username	Problem	Language	Result	Execution time	Memory
892149		box	Cake 3 (JOI19_cake3)	C++17	100 / 100	2318 ms	13320 KiB

cake3

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int N = 2e5, N_ = 1 << 18;
const i64 INF = 1e18;

int n, m;
int v[N], c[N], order[N];
vector<int> vv;
i64 best[N];

struct {
    i64 sum[N_ * 2]; int cnt[N_ * 2];
    void inc(int i, int x) {
        i += N_;
        sum[i] += x * vv[i - N_];
        cnt[i] += x;
        while (i /= 2) sum[i] = sum[i * 2] + sum[i * 2 + 1], cnt[i] = cnt[i * 2] + cnt[i * 2 + 1];
    }
    i64 qry(int x) {
        int i = 1;
        i64 s = 0;
        assert(x <= cnt[1]);
        while (i < N_) {
            if (cnt[i * 2 + 1] <= x) {
                x -= cnt[i * 2 + 1];
                s += sum[i * 2 + 1];
                i *= 2;
            } else i = i * 2 + 1;
        }
        assert(cnt[i] >= x);
        s += (i64) x * vv[i - N_];
        return s;
    }
} seg;

int pl = 0, pr = -1;

void upd(int i, int x) {
    seg.inc(order[i], x);
}

i64 qry(int l, int r) {
    if (r - l + 1 < m) return -INF;
    while (pl > l) upd(--pl, 1);
    while (pl < l) upd(pl++, -1);
    while (pr > r) upd(pr--, -1);
    while (pr < r) upd(++pr, 1);
    return seg.qry(m) - 2 * (c[r] - c[l]);
}

void rec(int l, int r, int low, int hi) {
    if (l <= r) {
        int m = (l + r) / 2, opt = low;
        best[m] = qry(m, opt);
        for (int i = low + 1; i <= hi; i++) {
            i64 x = qry(m, i);
            if (x > best[m]) best[m] = x, opt = i;
        }
        rec(l, m - 1, low, opt);
        rec(m + 1, r, opt, hi);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    vector<pair<int, int>> tmp;
    for (int i = 0; i < n; i++) {
        int v, c; cin >> v >> c;
        tmp.push_back({c, v});
        vv.push_back(v);
    }
    sort(begin(tmp), end(tmp));
    sort(begin(vv), end(vv));
    vv.erase(unique(begin(vv), end(vv)), end(vv));
    for (int i = 0; i < n; i++) {
        tie(c[i], v[i]) = tmp[i];
        order[i] = lower_bound(begin(vv), end(vv), v[i]) - begin(vv);
    }
    rec(0, n - m, 0, n - 1);
    cout << *max_element(best, best + n - m + 1) << '\n';
}

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