记录编号	146726	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]种树	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.278 s
提交时间	2015-01-19 12:02:02	内存使用	5.44 MiB

#include<cstdio>
char cha[2000000],*ptr=cha;
const int maxn=200010;
int pre[maxn],next[maxn],bet[maxn],heap[maxn];
bool c[maxn];
void in(int &x){
	bool fl=0;while(*ptr<40) ptr++;
	if(*ptr==45) fl=1,x=0;else x=*ptr-48;ptr++;
	while(*ptr>47) x=x*10+*ptr++-48;if(fl) x=-x;
}
void swap(int &x,int &y){
	x=x^y,y=x^y,x=x^y;
}
void push(int x){
	int now,next;
	heap[now=++heap[0]]=x;
	if(heap[0]==1) return;
	while(now>1){
		next=now>>1;
		if(bet[heap[next]]>=bet[x]) break;
		else swap(heap[next],heap[now]);
		now=next;
	}
}
int top(){
	int res=heap[1];
	heap[1]=heap[heap[0]--];
	int now=1,next;
	while(1){
		next=now<<1;
		if(next>heap[0]) break;
		if(next<heap[0]&&bet[heap[next+1]]>bet[heap[next]]) next++;
		if(bet[heap[next]]<=bet[heap[now]]) break;
		else swap(heap[next],heap[now]);
		now=next;
	}
	return res;
}
int main(){
	freopen("nt2011_tree.in","r",stdin);
	freopen("nt2011_tree.out","w",stdout);
	fread(ptr,1,2000000,stdin);
	int n,m,i,ans=0;
	in(n),in(m);
	if(m>(n>>1)){
		printf("Error!");
		return 0;
	}
	for(i=1;i<=n;i++) in(bet[i]),push(i),pre[i]=i-1,next[i]=i+1;
	pre[1]=n,next[n]=1;
	while(m--){
		int a=top();
		while(c[a]) a=top();
		int pe=pre[a],net=next[a],ppre=pre[pe],nnext=next[net];
		ans+=bet[a],bet[a]=bet[pe]+bet[net]-bet[a];
		next[ppre]=a,pre[nnext]=a,pre[a]=ppre,next[a]=nnext;
		push(a),c[pe]=c[net]=1;
	}
	printf("%d",ans);
}