Submission #1150470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150470		brinton	Feast (NOI19_feast)	C++20	0 / 100	104 ms	16572 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Node{
    Node *p,*child;
    int val;
    Node(int ival): p(nullptr),child(nullptr),val(ival) {};
};
signed main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //start here
    int N,K;cin >> N >> K;
    vector<int> v;
    int prev = 0;
    for(int i = 0;i < N;i++){
        int cur;cin >> cur;
        if(cur*prev < 0){
            if(!v.empty() || prev > 0){
                v.push_back(prev);
            }
            prev = cur;
        }else{
            prev += cur;
        }
    }
    v.push_back(prev);
    if(v.size() >= 1 && v.back() < 0)v.pop_back(); 
    // for(auto i:v)cout << i << " ";cout << endl;

    // greedy
    N = v.size();
    set<pair<int,Node*>> s;
    int ans = 0;
    int used = 0;
    vector<Node*> link;
    for(int i = 0;i < N;i++){
        link.push_back(new Node(v[i]));
        if(i != 0){
            link[i]->p = link[i-1];
            link[i-1]->child = link[i];
        }

        if(v[i] > 0){
            used++;
            ans += v[i];
        }
        s.insert({abs(v[i]),link[i]});
    }
    while(used > K){
        ans -= s.begin()->first;
        Node* cur = s.begin()->second;
        s.erase(s.begin());

        
        
        if(cur->p != nullptr){
            cur->val += cur->p->val;
            s.erase({abs(cur->p->val),cur->p});
            cur->p = cur->p->p;
            if(cur->p != nullptr)cur->p->child = cur;
        }
        
        if(cur->child != nullptr){
            cur->val+cur->child->val;
            s.erase({abs(cur->child->val),cur->p});
            cur->child = cur->child->child;
            if(cur->child != nullptr)cur->child->p = cur;
        }

        s.insert({cur->val,cur});
        used--;
    }
    cout << ans;
}

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