Submission #157117

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

cake3

#include<bits/stdc++.h>

using namespace std;

using LL = long long;
const LL infLL = (LL)1e18 + 123;

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 debug() {
    cerr << sumV << ' ' << smallestV << ' ' << rem << ' ' << inCnt << ' ';
    for (auto _ : cnt) cerr << _.first << '-' << _.second << ' '; cerr << '\n';
}

void add(int val) {
//    cerr << "+" << val << '\n';
    ++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;
//    debug();
}

void eli(int val) {
//    cerr << "-" << val << '\n';
    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;
            }
        }
        else if (val == smallestV) {
            if (rem == nSmallestV) {
                sumV -= val;
                smallestV = prev(cnt.lower_bound(smallestV) )->first;
                rem = 1;
                sumV += smallestV;
            }
        }
    }
    --inCnt;
//    debug();
}

void solve(int Left, int Right, int l, int r) {
    int Mid = (Left + Right) >> 1;
//    cerr << "Left = " << Left << "  Right = " << Right << "  Mid = " << Mid << "  " << l << ' ' << r << '\n';
    // (r, Right]
    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);
    // (min(Mid - 2, r), Right]
    for (int i = Right; i >= Mid; --i) eli(piece[i].v);
    // (min(Mid - 2, r), Mid)
    int opt = -1;
    for (int i = min(Mid - 2, r); i >= l; --i) {
//        cerr << i << ' ';
//        debug();
        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);
    }
//    cerr << f[Mid] << "===\n";
    // [l, Mid)
    for (int i = l; i <= opt; ++i) eli(piece[i].v);
    // (opt, Mid)
    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);
    // (r, Right]
    if (Mid < Right) solve(Mid + 1, Right, opt, r);
}

int main() {
//    freopen("input", "r", stdin);
//    freopen("output.txt", "w", stdout);

    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() );
//    for (auto ePiece : piece) cerr << ePiece.v << ' ' << ePiece.c << '\n';

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

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

    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void debug()':
cake3.cpp:22:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (auto _ : cnt) cerr << _.first << '-' << _.second << ' '; cerr << '\n';
     ^~~
cake3.cpp:22:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for (auto _ : cnt) cerr << _.first << '-' << _.second << ' '; cerr << '\n';
                                                                   ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:117: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:120: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