Submission #966866

#	Time	Username	Problem	Language	Result	Execution time	Memory
966866		ktsp2332	Feast (NOI19_feast)	C++14	71 / 100	188 ms	262144 KiB

feast

#include<bits/stdc++.h>
#define int long long

using namespace std;

int n,k, arr[300300], l, r, vis[300300], mx = -1e18, sum, now, ans, qs[300300], ck, idx;

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k;
    for(int i = 1; i<=n; ++i){
        cin >> arr[i];
        if(arr[i] < 0){
            ck++;
            idx = i;
        }
        qs[i] = qs[i - 1] + arr[i];
    }
    if(!ck){
        cout << qs[n];
        return 0;
    }
    if(ck == 1){
        if(k == 1) cout << max({qs[idx - 1], qs[n], qs[n] - qs[idx]});
        else cout << qs[n] - arr[idx];
        return 0;
    }
    if(k == 1){
        for(int i = 1; i<=n; ++i){
            sum+=arr[i];
            if(sum < 0) sum = 0;
            ans = max(ans, sum);
        }
        cout << ans;
        return 0;
    }
    int dp[n+1][k+1], mx[k+1];
    memset(dp, 0, sizeof(dp));
    memset(mx, 0, sizeof(mx));
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=k; j++) {
            dp[i][j] = dp[i-1][j];
            if(j) dp[i][j] = max(dp[i][j], qs[i] + mx[j-1]);
        }
 
        for(int j=0; j<=k; j++) mx[j] = max(mx[j], dp[i][j] - qs[i]);
    }
    cout << dp[n][k];
}

• 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: 0 / 29