Submission #401597

#	Time	Username	Problem	Language	Result	Execution time	Memory
401597		Fidisk	Feast (NOI19_feast)	C++14	40 / 100	95 ms	13204 KiB

feast

#include <bits/stdc++.h>
using namespace std;

#define oo 1e15
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;

const ll base=361;
const ll mod=998244353;
const ld eps=1e-5;
const ll maxn=1e6;

struct comp{
    bool operator() (pll x,pll y) {
        return x.fi>y.fi;
    }
};

ll sig(ll x) {
    if (x<0) {
        return -1;
    }
    return 1;
}

priority_queue<pll,vector<pll>,comp> heap;
ll n,k,i,a[400009],tmp,b[400009],m,l[400009],r[400009],res,cnt,cur;
bool ok[400009];

int main(){
    IO;
    cin>>n>>k;
    //cout<<n<<'\n';
    for (i=1;i<=n;i++) {
        cin>>a[i];
    }
    for (i=1;i<=n;i++) {
        if (sig(a[i])*sig(a[i-1])<0) {
            if (m==0&&cur<0) {
                cur=a[i];
            }
            else {
                //cout<<i<<'\n';
                m++;
                b[m]=cur;
                cur=a[i];
            }
        }
        else {
            cur+=a[i];
        }
        //cout<<cur<<'\n';
    }
    if (cur>0) {
        m++;
        b[m]=cur;
    }
    //cout<<m<<'\n';
    for (i=1;i<=m;i++) {
        //cout<<b[i]<<' ';
        l[i]=i+1;
        r[i]=i-1;
        if (b[i]>0) {
            cnt++;
        }
        heap.push({abs(b[i]),i});
    }
    //cout<<'\n';
    r[1]=0;
    l[m]=0;
    l[0]=1;
    r[m+1]=m;
    while (cnt>k) {
        while (b[l[0]]<0) {
            ok[l[0]]=true;
            l[0]=l[l[0]];
            r[l[0]]=0;
        }
        while (b[r[m+1]]<0) {
            ok[r[m+1]]=true;
            r[m+1]=r[r[m+1]];
            l[r[m+1]]=0;
        }
        ll y=heap.top().fi;
        ll x=heap.top().se;
        heap.pop();
        if (ok[x]) continue;
        //cout<<b[x]<<' '<<l[x]<<' '<<r[x]<<'\n';
        tmp=0;
        if (b[x]>0) {
            tmp++;
        }
        if (b[r[x]]>0) {
            tmp++;
        }
        if (b[l[x]]>0) {
            tmp++;
        }
        if (b[x]+b[l[x]]+b[r[x]]>0) {
            tmp--;
        }
        cnt-=tmp;
        ok[l[x]]=true;
        ok[r[x]]=true;
        b[x]=b[l[x]]+b[r[x]]+b[x];
        l[x]=l[l[x]];
        r[x]=r[r[x]];
        if (l[x]!=0) {
            r[l[x]]=x;
        }
        if (r[x]!=0) {
            l[r[x]]=x;
        }
        //if (b[x]>=0) {
            heap.push({abs(b[x]),x});
        //}
    }
    for (i=1;i<=m;i++) {
        if (!ok[i]&&b[i]>0) {
            res+=b[i];
        }
    }
    cout<<res<<'\n';
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:99:12: warning: unused variable 'y' [-Wunused-variable]
   99 |         ll y=heap.top().fi;
      |            ^

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