记录编号	156091	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]种树	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.250 s
提交时间	2015-04-02 10:45:55	内存使用	2.80 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x7fffffff;
const double eps=1e-10;
///==============struct declaration==============
struct Node{
	int x,val;
	Node (int x=0,int val=0):x(x),val(val){}
	bool operator <(const Node &rhs) const{
		return val<rhs.val;
	}
};
///==============var declaration=================
const int MAXN=200010;
int n,ans,m;
int w[MAXN];
int prev[MAXN],next[MAXN];
bool del[MAXN];
priority_queue <Node> Q;
///==============function declaration============

///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
   freopen("nt2011_tree.in","r",stdin);
   freopen("nt2011_tree.out","w",stdout);
	//#endif 
	scanf("%d%d",&n,&m);
	if (m>n/2){
		printf("Error!\n");
		return 0;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",w+i);
		prev[i]=i==1?n:i-1;
		next[i]=i==n?1:i+1;
		Q.push(Node(i,w[i]));
	}
	int Ans=0;
	while (m--){
		Node xx;int x;
		do{
			xx=Q.top();Q.pop();
			x=xx.x;
		}while (del[x]);
		Ans+=w[x];w[x]=w[prev[x]]+w[next[x]]-w[x];
		del[prev[x]]=del[next[x]]=true;
		next[prev[prev[x]]]=x;
		prev[x]=prev[prev[x]];
		prev[next[next[x]]]=x;
		next[x]=next[next[x]];
		Q.push(Node(x,w[x]));
	}
	printf("%d\n",Ans);
   return 0;
}
///================fuction code====================