这道题就贪心.... 正的一坨和负的一坨间隔
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #include<cstdlib> #define LL long long using namespace std; const int M=500007; LL read(){ LL ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } LL lx[M],rx[M],w[M]; LL n,k,tot; LL cnt=1; LL sum[M],ans; bool f[M]; struct node{ LL w,pos; bool operator<(const node &x) const{return w>x.w;} }; priority_queue<node>q; LL pd(LL x){return x>=0?x:-x;} int main() { //freopen("input.in","r",stdin); LL v; n=read(); k=read(); for(int i=1;i<=n;i++){ v=read(); if(v*sum[cnt]>=0) sum[cnt]+=v; else sum[++cnt]=v; } if(sum[1]*sum[cnt]>=0) sum[1]=sum[cnt]+sum[1],cnt--; for(int i=1;i<=cnt;i++) if(sum[i]>0) ans+=sum[i],tot++; //printf("%lld ",ans); if(tot<=k){printf("%lld ",ans); return 0;} LL now=tot-k; //printf("[%lld] ",ans); q.push((node){pd(sum[1]),1}); lx[1]=cnt; rx[1]=2; w[1]=pd(sum[1]); q.push((node){pd(sum[cnt]),cnt}); lx[cnt]=cnt-1; rx[cnt]=1; w[cnt]=pd(sum[cnt]); for(int i=2;i<cnt;i++) q.push((node){pd(sum[i]),i}),lx[i]=i-1,rx[i]=i+1,w[i]=pd(sum[i]);//printf("%d ",pd(sum[i])); //printf("[%d] ",now); while(now){ node x=q.top(); q.pop(); LL k=x.pos; if(f[k]) continue; //printf("%lld ",w[k]); ans-=w[k]; now--; LL l=lx[k],r=rx[k]; f[l]=1; f[r]=1; cnt++; sum[cnt]=sum[k]+sum[l]+sum[r]; w[cnt]=pd(sum[cnt]); q.push((node){w[cnt],cnt}); lx[cnt]=lx[l]; rx[cnt]=rx[r]; rx[lx[l]]=cnt; lx[rx[r]]=cnt; } //printf("%lld ",cnt); printf("%lld ",ans); return 0; }