Submission #1326519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326519		Gabriel	Feast (NOI19_feast)	C++20	30 / 100	33 ms	5040 KiB

feast

#include "bits/stdc++.h"
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin>>n>>k;
    k--;
    deque<long long> a(n);
    long long r = 0;
    for(int i = 0; i < n; i++) cin>>a[i];
    while(!a.empty() and a[0] < 0){
        a.pop_front();
    }
    while(!a.empty() and a.back() < 0){
        a.pop_back();
    }
    vector< pair<long long, pair<int, int> > > Borrar;
    long long Suma = 0;
    a.push_back(0);
    n = a.size();
    for(int i = 0; i < n; i++){
        if(a[i] < 0){
            if(Suma == 0) Borrar.push_back({0LL, {i, -2}});
            Suma += a[i];
        } else if(Suma != 0){
            Borrar.back().first = Suma;
            Borrar.back().second.second = i;
            Suma = 0;
        }
    }
    sort(Borrar.begin(), Borrar.end());
    for(int i = 0; i < k and i < Borrar.size(); i++){
        for(; Borrar[i].second.first < Borrar[i].second.second; Borrar[i].second.first++){
            a[Borrar[i].second.first] = -0;
        }
    }
    Suma = 0;
    for(auto E: a){
        Suma += E;
        Suma = max(0LL, Suma);
        r = max(Suma, r);
    }
    cout<<r;
    return 0;
}

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