Submission #697723

#	Time	Username	Problem	Language	Result	Execution time	Memory
697723		thomas_li	Feast (NOI19_feast)	C++17	100 / 100	199 ms	10592 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,k; cin >> n >> k;
    vector<int> a(n); for(int& v : a) cin >> v;
    partial_sum(a.begin(),a.end(),a.begin());
    auto go = [&](int c){
        vector<int> dp(n+1,-1e18),cnt(n+1);
        dp[0] = 0;
        pair<int,int> mx = {0,0};
        pair<int,int> bst = {-1e18,0};
        for(int i = 1; i <= n; i++){
            dp[i] = dp[i-1]; cnt[i] = cnt[i-1];
            auto[adj, cntj] = mx; cntj *= -1;
            if(adj-c+a[i-1] > dp[i]){
                dp[i] = adj-c+a[i-1];
                cnt[i] = cntj+1;
            }
            mx = max(mx,{dp[i]-a[i-1],-cnt[i]});
            bst = max(bst,{dp[i],-cnt[i]});
        }
        bst.second *= -1;
        bst.first += c*bst.second;
        return bst;
    };
    /*
    for(int i = 0; i <= 10; i++){
        auto[res,cnt] = go(i);
        cout << i << ": " << cnt << " " << res << "\n";
    }*/
    int lo = 0, hi = 1e12;
    while(lo < hi){
        int mid = (lo+hi)/2;
        auto[res,cnt] = go(mid);
        if(cnt <= k) hi = mid;
        else lo = mid+1;
    }
    cout << go(lo).first << "\n";
}
// dp[i] = max{mx[j]+psa[i]-psa[j]-c}

• 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