Submission #1160434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160434		Perl32	Cake 3 (JOI19_cake3)	C++20	24 / 100	177 ms	327680 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

constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

struct ST {
    vector<ll> 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, -inf);
    }

    void init(vector<ll>& a) {
        for (int i = 0; i < (int) a.size(); ++i) t[i + sz] = a[i];
        for (int i = sz - 1; i > 0; --i) pull(i);
    }

    ll get(int l, int r) {
        l += sz; r += sz;
        ll res = -inf;
        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, ll 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);
    tt.upd(0, 0ll);
    vector<vector<ll>> dp(K + 1, vector<ll>(N + 1));
    for (int k = 1; k < K; ++k) {
        for (int i = k; i <= N; ++i) {
            auto [c, v] = a[i];
            if (k == 1) {
                dp[k][i] = v + 2 * c;
            } else {
                dp[k][i] = tt.get(0, i) + v;
            }
        }
        tt.init(dp[k]);
    }
    ll ans = -inf;
    for (int i = K; i <= N; ++i) {
        auto [c, v] = a[i];
        ans = max(ans, v - 2 * c + tt.get(0, i));
    }
    cout << ans;
}

/*

 */

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