# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
503503 | jpark | Feast (NOI19_feast) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
}
}
}