# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
503503 | 2022-01-08T08:28:41 Z | jpark | Feast (NOI19_feast) | C++14 | 0 ms | 0 KB |
#include<iostream> using namespace std; int main(){ int n,k; cin >> n >> k; int arr[n]; int pre[n+1]; int negc = 0; int a; for(int x=0; x<n; x++){ cin >> a; arr[x] = a; pre[x] = 0; if(a<0) ++negc; } pre[n] = 0; int total = 0; if(negc==0){ for(int x=0; x<n; x++){ total += arr[x]; } cout << total; return; } if(negc==1){ if(k>=2){ for(int x=0; x<n; x++){ if(arr[x]>0){ total += arr[x]; } } cout << total; return; } else{ int all = 0; for(int x=0; x<n; x++){ all += arr[x]; } int before,after = 0; bool reached = false; for(int x=0; x<n; x++){ if(arr[x]<0){ reached = true; continue; } if(reached){ after += arr[x]; } else{ before += arr[x]; } } total = max(all,max(before,after)); } } if(k==1){ pre[0] = 0; for(int x=1; x<n+1; x++){ pre[x] = pre[x-1]+arr[x-1]; } int l,r = 0; while(r<n){ total = max(total,pre[r]-pre[l]); if(l==r){ ++r; continue; } } } }