제출 #157112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
157112		EntityIT	Cake 3 (JOI19_cake3)	C++14	0 / 100	2 ms	380 KiB

cake3

#include<bits/stdc++.h>

using namespace std;

#define int LL

using LL = long long;

int n, m, inCnt, smallestV, rem;
LL sumV;
map<int, int> cnt;
vector<LL> f;

struct Piece {
    int v, c;
    Piece(int _v = 0, int _c = 0) : v(_v), c(_c) {}
    bool operator<(const Piece &_) const { return make_pair(c, v) < make_pair(_.c, _.v); }
};
vector<Piece> piece;

void add(int val) {
    ++cnt[val];
    if (inCnt < m) {
        sumV += val;
        tie(smallestV, rem) = *cnt.begin();
    }
    else {
        if (val > smallestV) {
            sumV -= smallestV, sumV += val;
            if (rem == 1) tie(smallestV, rem) = *cnt.upper_bound(smallestV);
            else --rem;
        }
    }
    ++inCnt;
}

void eli(int val) {
    int nSmallestV = cnt[smallestV];
    --cnt[val];
    if (!cnt[val]) cnt.erase(val);
    if (inCnt <= m) {
        sumV -= val;
        tie(smallestV, rem) = *cnt.begin();
    }
    else {
        if (val >= smallestV) {
            if (rem == nSmallestV) {
                sumV -= val;
                smallestV = prev(cnt.lower_bound(smallestV) )->first;
                rem = 1;
                sumV += smallestV;
            }
            else {
                ++rem;
                sumV -= val;
                sumV += smallestV;
            }
        }
    }
    --inCnt;
}

void solve(int Left, int Right, int l, int r) {
    int Mid = (Left + Right) >> 1;
    if (Mid < m + 1) {
        if (Mid < Right) solve(Mid + 1, Right, l, r);
        return ;
    }
    for (int i = r; i >= Mid - 1; --i) add(piece[i].v);
    for (int i = Right; i >= Mid; --i) eli(piece[i].v);
    int opt = -1;
    for (int i = min(Mid - 2, r); i >= l; --i) {
        LL tmp = sumV - 2 * (piece[Mid].c - piece[i].c) + piece[Mid].v + piece[i].v;
        if (f[Mid] <= tmp) {
            f[Mid] = tmp;
            opt = i;
        }
        add(piece[i].v);
    }
    for (int i = l; i <= opt; ++i) eli(piece[i].v);
    if (Left < Mid) solve(Left, Mid - 1, l, opt);
    for (int i = Mid; i <= Right; ++i) add(piece[i].v);
    for (int i = opt + 1; i <= r; ++i) eli(piece[i].v);
    if (Mid < Right) solve(Mid + 1, Right, opt, r);
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("input", "r", stdin);

    cin >> n >> m; m -= 2;
    piece.assign(n, Piece() );
    for (int i = 0; i < n; ++i) {
        int v, c; cin >> v >> c;
        piece[i] = Piece(v, c);
    }
    sort(piece.begin(), piece.end() );

    f.assign(n, 0);
    solve(0, n - 1, 0, n - 1);

    LL ans = 0;
    for (LL ret : f) ans = max(ans, ret);
    cout << ans;

    return 0;
}

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