Submission #997176

#	Time	Username	Problem	Language	Result	Execution time	Memory
997176		anonymous321	Feast (NOI19_feast)	C++17	100 / 100	243 ms	13768 KiB

feast

// https://oj.uz/problem/view/NOI19_feast
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> a (n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    ll ans = 0;
    ll lo = 0;
    ll hi = 1LL << 55;
    while (lo < hi) {
        ll mid = lo + (hi - lo)/2;
        vector<ll> dp (n+1, 0);
        vector<ll> p (n+1, 0);
        ll best = 0;
        int id = 0;
        vector<int> cnt (n+1, 0);
        for (int i = 0; i < n; i++) {
            p[i+1] = p[i] + a[i];
            dp[i+1] = dp[i];
            cnt[i+1] = cnt[i];
            if (dp[i+1] < best + p[i+1] - mid) {
                dp[i+1] = best + p[i+1] - mid;
                cnt[i+1] = cnt[id] + 1;
            }
            if (best < dp[i+1] - p[i+1]) {
                best = dp[i+1] - p[i+1];
                id = i+1;
            }
        }
        
        if (cnt[n] <= k) {
            hi = mid;
            ans = dp[n];
        } else {
            lo = mid+1;
        }
    }
    cout << ans + k*hi << "\n";
    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