Submission #1137024

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

cake3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 200'000;
const ll INF = 1000'000'000'000'000'000;
const ll BIG = 1'000'000'000'000;

int n, m;
ll a[N + 10], c[N + 10], v[N + 10];
pair<ll, int> dp[N + 10][4];
pair<ll, ll> p[N + 10];

void readInput() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> p[i].second >> p[i].first;
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; i++) {
        c[i] = p[i].first;
        a[i] = p[i].second;
    }
}

void calcDP(int i, int t) {
    pair<ll, int> case1 = dp[i - 1][t];
    pair<ll, int> case2 = {dp[i - 1][t - 1].first + v[i], dp[i - 1][t - 1].second + 1};
    if (t == 1)
        case2.first += c[i] * 2ll;
    dp[i][t] = max(case1, case2);
    if (t == 2) {
        pair<ll, int> case3 = {dp[i - 1][t].first + v[i], dp[i - 1][t].second + 1};
        dp[i][t] = max(dp[i][t], case3);
    }
}

void calcDP() {
    for (int i = 0; i <= n; i++)
        for (int t = 0; t <= 2; t++)
            dp[i][t] = {-INF, 0};
    dp[0][0] = {0, 0};
    for (int i = 1; i <= n; i++) {
        dp[i][0] = {0, 0};
        for (int t = 1; t <= 2; t++)
            calcDP(i, t);
    }
}

pair<ll, int> calcDP(ll x) {
    for (int i = 1; i <= n; i++)
        v[i] = a[i] - x;
    calcDP();
    pair<ll, int> res = {-INF, -1};
    for (int i = 3; i <= n; i++) {
        pair<ll, int> tmp = {dp[i - 1][2].first + v[i] - c[i] * 2ll, dp[i - 1][2].second + 1};
        res = max(res, tmp);
    }
    return res;
}

void calcAns() {
    ll l = -BIG, r = +BIG;
    while (r - l > 1) {
        ll mid = (l + r) >> 1;
        pair<ll, int> res = calcDP(mid);
        if (res.second >= m)
            l = mid;
        else
            r = mid;
    }
    pair<ll, int> res = calcDP(l);
    cout << res.first + l * m << flush;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcAns();
    return 0;
}

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