Submission #1146552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146552		KhoaDuy	Feast (NOI19_feast)	C++20	12 / 100	52 ms	10748 KiB

feast

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    cin >> n;
    int a[n+1];
    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(a[i]*a[j]<0){
                break;
            }
            sum+=a[j];
        }
        i=j-1;
        if(sum<=0&&b.empty()){
            continue;
        }
        b.push_back(sum);
    }
    if(b.empty()){
        cout << 0 << endl;
        return 0;
    }
    if(b.back()<=0){
        b.pop_back();
    }
    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++){
        if(b[i]>0){
            cnt++;
            ans+=b[i];
        }
        le[i]=i-1;
        ri[i]=i+1;
        pq.push({abs(b[i]),i});
    }
    if(cnt<=k){
        cout << ans << endl;
        return 0;
    }
    while(cnt>k){
        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){
            b[idx]+=b[le[idx]];
            nxtle=le[le[idx]];
            del[le[idx]]=true;
        }
        if(ri[idx]<b.size()){
            b[idx]+=b[ri[idx]];
            nxtri=ri[ri[idx]];
            del[ri[idx]]=true;
        }
        le[idx]=nxtle,ri[idx]=nxtri;
        pq.push({abs(b[idx]),idx});
    }
    cout << ans << endl;
}

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