Submission #1141153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141153		anmattroi	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	328 KiB

cake3

/*******************************************

Task: JOI19_Cake3
Link: https://oj.uz/problem/view/JOI19_cake3

*******************************************/

#include <bits/stdc++.h>
#define maxn 200005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
using li = pair<int64_t, int>;

int n, k;
ii a[maxn];
li f[maxn];


li solve_lambda(int64_t lambda) {
    li mx = {LLONG_MIN/100, 0};
    for (int i = 1; i <= n; i++) {
        f[i] = {a[i].fi + 2LL * a[i].se - lambda, 1};
        f[i] = max(f[i], li{mx.fi+a[i].fi - lambda, mx.se+1});
        mx = max(mx, f[i]);
    }
    mx = {LLONG_MIN, 0};
    for (int i = 1; i <= n; i++) mx = max(mx, li{f[i].fi - 2LL * a[i].se, f[i].se});
    return mx;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + n + 1, [&](ii x, ii y) {return x.se < y.se;});

    li mx = {-1, 0};

    for (int i = 1; i <= n; i++) {
        f[i] = {a[i].fi + 2LL * a[i].se, 1};
        f[i] = max(f[i], li{mx.fi+a[i].fi, mx.se+1});
        mx = max(mx, f[i]);
    }

    mx = {LLONG_MIN, 0};
    for (int i = 1; i <= n; i++) mx = max(mx, li{f[i].fi - 2LL * a[i].se, f[i].se});

    if (mx.se >= k) {
        int64_t lo = 0, hi = LLONG_MAX/10;
        while (hi - lo > 1) {
            int64_t mid = (lo + hi) >> 1LL;
            if (solve_lambda(mid).se >= k) lo = mid;
            else hi = mid;
        }
        cout << solve_lambda(lo).fi + k * lo;
        exit(0);
    } else {
        int64_t lo = -5000000000LL, hi = 1;
         while (hi - lo > 1) {
            int64_t mid = (lo + hi) >> 1LL;
            if (solve_lambda(mid).se >= k) lo = mid;
            else hi = mid;
        }
        cout << solve_lambda(lo).fi + max(solve_lambda(lo).se, k) * lo << "\n";
        exit(0);
    }
}

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