Submission #1313690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313690		spicytomato	Feast (NOI19_feast)	C++20	4 / 100	71 ms	21868 KiB

feast

#include <bits/stdc++.h>

using namespace std;

long long n,k,x,ans=0,cnt=0,f=1,lnei[600001]={0},rnei[600001]={0},l[600001]={0},r[600001]={0},vld[600001]={0},sum[600001]={0},sta[600001];
vector<long long> a,val;
priority_queue<pair<long long,int> > q;

void solve() 
{
    a.push_back(0);
    val.push_back(0);
    cin>>n>>k;
    for(int i=1;i<=n;i+=1) 
    {
        cin>>x;
        if(x!=0) a.push_back(x);
    }
    n=a.size()-1;
    k=min(k,n);
    int ind=1;
    while(ind<a.size() && a[ind]<0) ind+=1;
    if(ind==a.size()) 
    {
        cout<<0;
        return;
    }
    long long pre=0;
    for(int i=ind;i<=n;i+=1)
    {
        if(f*a[i]>0) pre+=a[i];
        else
        {
            if(pre>0) 
            {
                ans+=pre;
                cnt+=1;
            }
            val.push_back(pre);
            pre=a[i];
            f=-f;
        }
    }
    if(pre>0)
    {
        ans+=pre;
        cnt+=1;
    }
    val.push_back(pre);
    //for(int i=1;i<val.size();i+=1) cout<<val[i]<<" ";
    if(cnt<=k)
    {
        cout<<ans;
        return;
    }
    int tot=val.size()-1;
    for(int i=1;i<=tot;i+=1) sum[i]=val[i]+sum[i-1];
    for(int i=1;i<=tot;i+=1)
    {
        l[i]=r[i]=i;
        lnei[i]=i-1;
        rnei[i]=(i+1)%(tot+1);
        vld[i]=1;
        sta[i]=val[i]/abs(val[i]);
        q.push(make_pair(-abs(a[i]),i));
    }
    while(cnt>k && q.size()>0)
    {
        long long d=q.top().first;
        int id=q.top().second;
        q.pop();
        if(vld[id]==0) continue;
        ans+=d;
        vld[id]=0;
        if(vld[lnei[id]]==1 && vld[rnei[id]]==1) cnt-=1;
        else if(sta[id]==1) cnt-=1;
        tot+=1;
        vld[tot]=1;
        sta[tot]=-sta[id];
        lnei[tot]=lnei[lnei[id]];
        rnei[tot]=rnei[rnei[id]];
        l[tot]=vld[lnei[id]]==1 ? l[lnei[id]] : l[id];
        r[tot]=vld[rnei[id]]==1 ? r[rnei[id]] : r[id];
        if(vld[lnei[tot]]==1) rnei[lnei[tot]]=tot;
        if(vld[rnei[tot]]==1) lnei[rnei[tot]]=tot;
        if(sta[tot]==-1) q.push(make_pair(sum[r[tot]]-sum[l[tot]-1],tot));
        else q.push(make_pair(-sum[r[tot]]+sum[l[tot]-1],tot));
        vld[id]=vld[lnei[id]]=vld[rnei[id]]=0;
    }
    cout<<ans;
}  

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

• Subtask 1: 4 / 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