Submission #966864

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
966864	2024-04-20T13:58:03 Z	ktsp2332	Feast (NOI19_feast)	C++14	Compilation error	0 ms	0 KB

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;
    }
    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];
}

Compilation message

feast.cpp: In function 'int main()':
feast.cpp:21:9: error: return-statement with no value, in function returning 'int' [-fpermissive]
   21 |         return;
      |         ^~~~~~