Submission #1160449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160449		Perl32	Cake 3 (JOI19_cake3)	C++20	0 / 100	0 ms	328 KiB

cake3

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

using i128 = __int128;
using T = pair<i128, int>;

constexpr ll inf = 1e15;
constexpr i128 infl = 1e20;

struct ST {
    vector<T> t;
    int sz;

    void pull(int i) {
        t[i] = max(t[i << 1], t[i << 1 | 1]);
    }

    ST(int n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        t.resize(sz << 1, T(-infl, 0));
    }

    T get(int l, int r) {
        l += sz; r += sz;
        T res = {-infl, 0};
        while (l < r) {
            if (l & 1) res = max(res, t[l++]);
            if (r & 1) res = max(res, t[--r]);
            l >>= 1; r >>= 1;
        }
        return res;
    }

    void upd(int i, T v) {
        i += sz;
        t[i] = v;
        i >>= 1;
        while (i) {
            pull(i);
            i >>= 1;
        }
    }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<array<ll, 2>> a(N + 1);
    for (int i = 1; i <= N; ++i) cin >> a[i][1] >> a[i][0];
    sort(a.begin() + 1, a.end());
    ST tt(N + 1);
    auto slv = [&](ll p) -> T {
        T res = {-infl, 0};
        for (int i = 1; i <= N; ++i) {
            auto [c, v] = a[i];
            T cur = T(v + 2 * c + p, 1);
            if (i > 1) {
                auto [pre, cnt] = tt.get(1, i);
                cur = max(cur, T(pre + v + p, cnt + 1));
                res = max(res, {pre + v + p - 2 * c, cnt + 1});
            }
            tt.upd(i, cur);
        }
        return res;
    };
    ll lx = -inf, rx = inf;
    while (lx + 1 < rx) {
        ll mid = (lx + rx) >> 1;
        if (slv(mid).second < K) {
            lx = mid;
        } else {
            rx = mid;
        }
    }
    cout << ll(slv(rx).first - K * rx);
}

/*

 */

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