Submission #157111

#	Time	Username	Problem	Language	Result	Execution time	Memory
157111		EntityIT	Cake 3 (JOI19_cake3)	C++14	0 / 100	3 ms	504 KiB

cake3

#include<bits/stdc++.h>

using namespace std;

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);
}

int main() {
//    freopen("input", "r", stdin);

    scanf(" %d %d", &n, &m); m -= 2;
    piece.assign(n, Piece() );
    for (int i = 0; i < n; ++i) {
        int v, c; scanf(" %d %d", &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;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d %d", &n, &m); m -= 2;
     ~~~~~^~~~~~~~~~~~~~~~~~
cake3.cpp:91:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int v, c; scanf(" %d %d", &v, &c);
                   ~~~~~^~~~~~~~~~~~~~~~~~

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