제출 #1150495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150495		brinton	Feast (NOI19_feast)	C++20	100 / 100	132 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((__int128_t)cur*prev < 0){
            if(!v.empty() || prev > 0){
                v.push_back(prev);
            }
            prev = cur;
        }else{
            prev += cur;
        }
    }
    if(prev != 0)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]});
    }
    // cout << endl << "throw start" << endl;;
    while(used > K){
    	// cout << used << "(" << ans << ") :" << endl;
    	// for(auto [a,b]:s){
    	// 	cout << a << " " << b->val << endl;
    	// }
        ans -= s.begin()->first;
        Node* cur = s.begin()->second;
        s.erase(s.begin());
        
        if(cur->p == nullptr || cur->child == nullptr){
        	assert(cur->val > 0);
        	
            if(cur->p == nullptr){
                s.erase({abs(cur->child->val),cur->child});
                if(cur->child->child != nullptr)cur->child->child->p = nullptr;
            }else{
                s.erase({abs(cur->p->val),cur->p});
                if(cur->p->p != nullptr)cur->p->p->child = nullptr;
            }
        }else{
            cur->val = cur->val+cur->p->val+cur->child->val;
            s.erase({abs(cur->p->val),cur->p});
            s.erase({abs(cur->child->val),cur->child});
            
            cur->p = cur->p->p;
            if(cur->p != nullptr)cur->p->child = cur;
            
            
            cur->child = cur->child->child;
            if(cur->child != nullptr)cur->child->p = cur;
            
            s.insert({abs(cur->val),cur});
        }
        

        
        used--;
    }
    cout << ans;
}
/*
65530729645
23746736887
*/

• 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