제출 #1159468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159468		KhoaDuy	Feast (NOI19_feast)	C++17	100 / 100	57 ms	10556 KiB

feast

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
int group(int x){
    if(x>=0){
        return 1;
    }
    return 0;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q=1;
    cin >> n;
    int a[n+1];
    while(q--){
        int ope=2;
        //cin >> ope;
        if(ope==1){
            int i,v;
            cin >> i >> v;
            a[i]=v;
        }
        else{
            int l=1,r=n,k;
            cin >> k;
            for(int i=1;i<=n;i++){
                cin >> a[i];
            }
            vector<int> b;
            for(int i=l;i<=r;i++){
                int sum=0;
                int j;
                for(j=i;j<=r;j++){
                    if(j>i&&group(a[j])!=group(a[j-1])){
                        break;
                    }
                    sum+=a[j];
                }
                i=j-1;
                b.push_back(sum);
            }
            if(b[0]<0){
                b.erase(b.begin());
            }
            if(b.empty()){
                cout << 0 << endl;
                continue;
            }
            if(b.back()<0){
                b.pop_back();
            }
            if(b.empty()){
                cout << 0 << endl;
                continue;
            }
            int ans=0,cnt=0;
            int le[b.size()],ri[b.size()];
            bool del[b.size()]={false};
            priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
            for(int i=0;i<b.size();i++){
                le[i]=i-1;
                ri[i]=i+1;
                pq.push({abs(b[i]),i});
            }
            for(int i=0;i<b.size();i+=2){
                ans+=b[i];
                cnt++;
            }
            if(cnt<=k){
                cout << ans << endl;
                continue;
            }
            int temp=0;
            for(int i=4;i<b.size();i++){
                temp+=b[i];
            }
            while(cnt>k&&!pq.empty()){
                int idx=pq.top().second,val=pq.top().first;
                pq.pop();
                if(del[idx]){
                    continue;
                }
                cnt--;
                ans-=val;
                int nxtle=-1,nxtri=b.size();
                if(le[idx]>=0&&!del[le[idx]]){
                    b[idx]+=b[le[idx]];
                    nxtle=le[le[idx]];
                    del[le[idx]]=true;
                }
                if(ri[idx]<b.size()&&!del[ri[idx]]){
                    b[idx]+=b[ri[idx]];
                    nxtri=ri[ri[idx]];
                    del[ri[idx]]=true;
                }
                bool border=false;
                if(le[idx]<0||ri[idx]>=b.size()){
                    border=true;
                }
                if(nxtle>=0){
                    if(!border){
                        ri[nxtle]=idx;
                    }
                    else{
                        ri[nxtle]=b.size();
                    }
                }
                if(nxtri<b.size()){
                    if(!border){
                        le[nxtri]=idx;
                    }
                    else{
                        le[nxtri]=-1;
                    }
                }
                le[idx]=nxtle,ri[idx]=nxtri;
                if(!border){
                    pq.push({abs(b[idx]),idx});
                }
            }
            if(cnt>k){
                cout << 0 << endl;
                continue;
            }
            cout << ans << endl;
        }
    }
}

• 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