#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;
| ^~~~~~
