제출 #1288356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288356		aduwahi	Cake 3 (JOI19_cake3)	C++20	0 / 100	0 ms	332 KiB

cake3

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

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

    int N, M;
    cin >> N >> M;
    vector<pair<ll,ll>> a(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i].first >> a[i].second; // V, C

    sort(a.begin(), a.end(), [](auto &x, auto &y){ return x.second < y.second; });

    vector<ll> pref(N+1, 0);
    for (int i = 0; i < N; ++i) pref[i+1] = pref[i] + a[i].first;

    vector<ll> gap(N-1);
    for (int i = 0; i < N-1; ++i) gap[i] = a[i+1].second - a[i].second;

    // Sparse table for range maximum on gaps
    int LOG = 20;
    vector<vector<ll>> st(LOG, vector<ll>(N-1));
    st[0] = gap;
    for (int k = 1; (1 << k) <= N-1; ++k)
        for (int i = 0; i + (1 << k) <= N-1; ++i)
            st[k][i] = max(st[k-1][i], st[k-1][i + (1 << (k-1))]);

    auto range_max = [&](int l, int r) {
        if (l > r) return 0LL;
        int len = r - l + 1;
        int k = __lg(len);
        return max(st[k][l], st[k][r - (1 << k) + 1]);
    };

    ll ans = LLONG_MIN;
    for (int i = 0; i + M <= N; ++i) {
        ll sumV = pref[i+M] - pref[i];
        ll range = a[i+M-1].second - a[i].second;
        ll largest_gap = range_max(i, i+M-2);
        ll beauty = sumV - 2 * range + largest_gap;
        ans = max(ans, beauty);
    }

    cout << ans << "\n";
    return 0;
}

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