제출 #1316517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316517		Lakshya108	Feast (NOI19_feast)	C++20	100 / 100	105 ms	5076 KiB

feast

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

pair<long long,int> calc(const vector<long long>& a, long long p) {
    int n = a.size();
    vector<long long> pref(n+1);
    for (int i = 0; i < n; i++) pref[i+1] = pref[i] + a[i];

    long long dp = 0, best = 0;
    int cnt = 0, bestc = 0;

    for (int i = 1; i <= n; i++) {
        long long v1 = dp;
        int c1 = cnt;

        long long v2 = best + pref[i] - p;
        int c2 = bestc + 1;

        if (v2 > v1 || (v2 == v1 && c2 > c1)) {
            dp = v2;
            cnt = c2;
        }

        long long cur = dp - pref[i];
        if (cur > best || (cur == best && cnt > bestc)) {
            best = cur;
            bestc = cnt;
        }
    }
    return {dp, cnt};
}

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

    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    auto base = calc(a, 0);
    if (base.second <= k) {
        cout << base.first;
        return 0;
    }

    long long l = 1, r = 1e14;
    while (l <= r) {
        long long m = (l + r) >> 1;
        if (calc(a, m).second > k) l = m + 1;
        else r = m - 1;
    }

    auto res = calc(a, l);
    cout << res.first + l * res.second;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29