记录编号	214774	评测结果	AAAAAAAAAA
题目名称	468.[NOI 2010]超级钢琴	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	1.947 s
提交时间	2015-12-17 20:57:36	内存使用	40.37 MiB

#define LL long long

#include<queue>
#include<cstdio>

using namespace std;

LL Ans;
int rmq[500010][20];
int n,K,L,R,s[500010],Mi[20],len,t;

struct Define{
	int l,r,d,val,del;
	friend bool operator < (Define A,Define B){
		return A.val<B.val;
	} 
}tmp,Top;

priority_queue<Define>q;

inline int in(){
	int x=0,c=getchar();
	bool flag=false;
	while(c<'0'||c>'9'){
		if(c=='-') flag=true;
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	if(flag) return -x;
	return x;
}

inline int Query(int l,int r)
{
	len=r-l+1;t=0;while((1<<t)<=len)t++;t--;
	return s[rmq[l][t]]<s[rmq[r-(1<<t)+1][t]]?rmq[l][t]:rmq[r-(1<<t)+1][t];
}

int main()
{
	freopen("piano.in","r",stdin);
	freopen("piano.out","w",stdout);
	n=in();K=in();L=in();R=in();Mi[0]=1;
	for(int i=1;i<=n;i++)Mi[i]=Mi[i-1]<<1;
	for(int i=1;i<=n;i++)s[i]=in()+s[i-1];
	for(int i=0;i<=n;i++)rmq[i][0]=i;
	for(int l=1,k=1;Mi[k]<=n;k++,l<<=1)for(int i=0,t=n-l+1;i<=t;i++)
		rmq[i][k]=s[rmq[i][k-1]]<s[rmq[i+l][k-1]]?rmq[i][k-1]:rmq[i+l][k-1];
	for(int i=1,l,r;i<=n;i++){
		if(i-L+1<=0)continue;r=i-L+1;l=i-R+1<1?1:i-R+1;
		tmp.del=Query(l-1,r-1)+1;
		q.push((Define){l,r,i,s[i]-s[tmp.del-1],tmp.del});
	}
	for(int i=1;i<=K;i++){
		Top=q.top();Ans+=Top.val;q.pop();
		tmp.d=Top.d;tmp.l=Top.l;tmp.r=Top.del-1;
		if(tmp.l<=tmp.r){
			tmp.del=Query(tmp.l-1,tmp.r-1)+1;
			tmp.val=s[tmp.d]-s[tmp.del-1];
			q.push(tmp);
		}
		tmp.l=Top.del+1;tmp.r=Top.r;
		if(tmp.l<=tmp.r){
			tmp.del=Query(tmp.l-1,tmp.r-1)+1;
			tmp.val=s[tmp.d]-s[tmp.del-1];
			q.push(tmp);
		}
	}
	printf("%lld",Ans);
}