Submission #386351

#	Time	Username	Problem	Language	Result	Execution time	Memory
386351		Aryan_Raina	Feast (NOI19_feast)	C++14	100 / 100	177 ms	12780 KiB

feast

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

#define int long long
#define ld long double
#define ar array

const int INF = 1e15;
const int MOD = 1e9+7;

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, k; cin>>n>>k;
    vector<int> a(n);
    for (int &i : a) cin>>i;
    vector<int> pf(n+1);
    pf[0] = 0; for (int i = 1; i <= n; i++) pf[i] = pf[i-1] + a[i-1];
    int dp[n+1], cnt[n+1];
    auto compute = [&](int lambda) {
        dp[0] = cnt[0] = 0;
        int besti = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i-1], cnt[i] = cnt[i-1];
            if (dp[i] < dp[besti] + pf[i] - pf[besti] - lambda) {
                dp[i] = dp[besti] + pf[i] - pf[besti] - lambda;
                cnt[i] = cnt[besti] + 1;
            }
            if (dp[besti] - pf[besti] < dp[i] - pf[i]) besti = i;
        }
    };
    int lo = 0, hi = 1e18, mid;
    while (lo + 1 < hi) {
        mid = (lo + hi) >> 1;
        compute(mid);
        if (cnt[n] <= k) {
            hi = mid;
        } else lo = mid+1;
    }
    compute(hi);
    cout<<dp[n] + cnt[n]*hi<<"\n";
}  

• 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