Submission #1316583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316583		gamigafy	Feast (NOI19_feast)	C++20	100 / 100	927 ms	23932 KiB

feast

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

using ll = long long;
#define sz(x) (int)(x).size()

void solve() {
    int n, k;
    cin >> n >> k;

    vector<ll> a(n);
    for (auto &x : a) cin >> x;

    auto chk = [&](ll lam) {
        vector dp(n + 1, vector<pair<ll, int>>(2, {-1E18, -1E18}));
        dp[0][0] = {0, 0};
        for (int i = 0; i < n; i++) {
            dp[i + 1][0] = max(dp[i][0], dp[i][1]);
            dp[i + 1][1] = max(
                make_pair(dp[i][1].first + a[i], dp[i][1].second),
                make_pair(dp[i][0].first + a[i] - lam, dp[i][0].second + 1)
            );
        }
        return max(dp[n][0], dp[n][1]);
    };

    ll l = 0, r = 1E18;
    while (l < r) {
        ll mid = (l + r + 1) / 2;
        auto [_, cnt] = chk(mid);
        if (cnt >= k) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    cout << chk(l).first + l * k << '\n';
}

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

    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

• 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