BZOJ3502PA2012Tanie linie&BZOJ2288[POJ Challenge]生日礼物——模拟费用流+链表+堆

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define pr pair<ll,int>
using namespace std;
ll s[1000010];
int pre[1000010];
int suf[1000010];
int vis[1000010];
int tot;
int n,k;
ll ans,x;
priority_queue< pr,vector<pr>,greater<pr> >q;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		if(x>0)
		{
			ans+=x;
			if(s[tot]>0)
			{
				s[tot]+=x;
			}
			else
			{
				s[++tot]=x;
			}
		}
		if(x<0)
		{
			if(s[tot]<=0)
			{
				s[tot]+=x;
			}
			else
			{
				s[++tot]=x;
			}
		}
	}
	if(s[tot]<=0)
	{
		tot--;
	}
	n=tot;
	if((n+1)/2<=k)
	{
		printf("%lld",ans);
		return 0;
	}
	k=(n+1)/2-k;
	for(int i=1;i<=n;i++)
	{
		pre[i]=i-1;
		suf[i]=i+1;
		s[i]=abs(s[i]);
		q.push(make_pair(s[i],i));
	}
	suf[n]=0;
	while(k--)
	{
		while(vis[q.top().second])q.pop();
		ans-=q.top().first;
		int now=q.top().second;
		q.pop();
		vis[pre[now]]=vis[suf[now]]=1;
		if(pre[now]&&suf[now])
		{
			s[now]=s[pre[now]]+s[suf[now]]-s[now];
			q.push(make_pair(s[now],now));
			pre[now]=pre[pre[now]];
			suf[now]=suf[suf[now]];
			if(pre[now])
			{
				suf[pre[now]]=now;
			}
			if(suf[now])
			{
				pre[suf[now]]=now;
			}
		}
		else
		{
			vis[now]=1;
			pre[now]=pre[pre[now]];
			suf[now]=suf[suf[now]];
			if(pre[now])
			{
				suf[pre[now]]=suf[now];
			}
			if(suf[now])
			{
				pre[suf[now]]=pre[now];
			}
		}
	}
	printf("%lld",ans);
}