Submission #1193123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193123		loom	Feast (NOI19_feast)	C++20	100 / 100	277 ms	21528 KiB

feast

#include<bits/stdc++.h>
#define int long long
#define nl endl
using namespace std;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);

    int n, k;
    cin>>n>>k;
    int a[n];
    for(int i=0; i<n; i++) cin>>a[i];

    set<pair<int,int> > idx;
    set<pair<pair<int,int>, int> > main;
    int sum = a[0];
    for(int i=1; i<n; i++){
        if(a[i] == 0) continue;
        if((a[i] >= 0 and a[i-1] >= 0) or (a[i] <= 0 and a[i-1] <= 0)){
            sum += a[i];
        }else{
            idx.insert(make_pair(i, sum));
            sum = a[i];
        }
    }
    idx.insert(make_pair(n, sum));

    if((*idx.begin()).second < 0) idx.erase(idx.begin());
    if(idx.size() > 1 and (*prev(idx.end())).second < 0) idx.erase(prev(idx.end()));

    for(auto x : idx){
        main.insert(make_pair(make_pair(abs(x.second), (x.second > 0)), x.first));
    }

    while((main.size()+1)/2 > k){
        int x = (*main.begin()).first.first * ((*main.begin()).first.second ? 1 : -1), i = (*main.begin()).second;
        auto it = idx.find(make_pair(i, x));

        pair<int,int> l = make_pair(0,0), r = make_pair(0,0);
        if(it != idx.begin()) l = *prev(it);
        if(next(it) != idx.end()) r = *next(it);

        main.erase(main.begin());
        main.erase(make_pair(make_pair(abs(l.second), (l.second > 0)), l.first));
        main.erase(make_pair(make_pair(abs(r.second), (r.second > 0)), r.first));
        main.insert(make_pair(make_pair(abs(x + l.second + r.second), (x + l.second + r.second > 0)), i));

        if(it != idx.begin()) idx.erase(prev(it));
        if(next(it) != idx.end()) idx.erase(next(it));
        idx.erase(it);
        idx.insert(make_pair(i, x + l.second + r.second));

        auto rem = idx.find(make_pair(i, x + l.second + r.second));
        if((rem == idx.begin() or next(rem) == idx.end()) and x > 0){
            main.erase(make_pair(make_pair(abs(x + l.second + r.second), (x + l.second + r.second > 0)), i));
            idx.erase(rem);
        }
    }

    sum = 0;
    for(auto x : main){
        if(x.first.second) sum += x.first.first;
    }

    cout<<sum;
    return 0;
}

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