Submission #1129030

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

cake3

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

typedef long long ll;

const int N = 200'000;
const ll INF = 100'000'000'000;

int n, m;
ll a[N + 10], c[N + 10], ans;
ll v[N + 10];
pair<ll, ll> p[N + 10];
pair<ll, int> dp[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;
    }
}

pair<ll, int> calcDP(ll x) {
    for (int i = 1; i <= n; i++)
        v[i] = a[i] + x;
    pair<ll, int> mx = {-INF, 0};
    pair<ll, int> res = {0ll, 0};
    for (int i = 1; i <= n; i++) {
        pair<ll, int> case1 = {mx.first + v[i], mx.second + 1};
        pair<ll, int> case2 = {v[i] + 2ll * c[i], 1};
        dp[i] = max(case1, case2);
        mx = max(mx, dp[i]);
        if (i == 1)
            res = {v[i], 1};
        else
            res = max(res, make_pair(dp[i].first - 2ll * c[i], dp[i].second));
    }
    return res;
}

void solve() {
    ll l = -INF, r = INF;
    while (r - l > 1) {
        ll mid = (l + r) / 2ll;
        if (calcDP(mid).second < m)
            l = mid;
        else
            r = mid;
    } 
    pair<ll, int> ans = calcDP(r);
    cout << ans.first - r * ans.second << flush;
}

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

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