Submission #1228905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228905		ripolas	Feast (NOI19_feast)	C++20	12 / 100	75 ms	3424 KiB

feast

#include <bits/stdc++.h>
using namespace std;
const int INF = 10e8;
#define int long long
signed main(){
  int n,k;
  cin>>n>>k;
  if(k!=1){
    vector<int> a (n);
    int ans = 0;
    int ansL = 0;
    int ansR = 0;
    bool startR = false;
    for(int i = 0;i<n;i++){
      cin>>a[i];
      ans+=a[i];
      if(startR){
        ansR+=a[i];
      }
      if(a[i]<0){
        ansL = ans-a[i];
        startR = true;
      }
    }
    if(k==1){
      cout<<max({ans,ansL,ansR})<<endl;
    }else{
      cout<<max({ans,ansL+ansR})<<endl;
    }
  }else{ // k = 1
    vector<int> costs;
    vector<int> segments;
    segments.push_back(0);
    for(int i = 0;i<n;i++){
      int a;
      cin>>a;
      if(a>=0){
        segments[segments.size()-1]+=a;
      }else{
        segments.push_back(0);
        costs.push_back(a);
      }
    }
    int m = segments.size();
    int ans = 0;
    int current = segments[0];
    for(int i = 1;i<m;i++){
      if(current+segments[i]+costs[i-1]>segments[i]&&current+segments[i]+costs[i-1]>current){
        current += segments[i]+costs[i-1]; 
        ans = max(current,ans);
      }else{
        ans = max(current,ans);
        current = segments[i];
        ans = max(current,ans);
      }
    }
    cout<<ans<<endl;
  }
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29