记录编号	429152	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	1.107 s
提交时间	2017-07-26 18:05:27	内存使用	33.82 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int M=500000+10;
int n,k,l,r;
int mn[M],st[M][20],val[M];
long long ans;
struct DATE{int le,fr,to,ri;};
priority_queue<DATE> pq;
inline bool operator < (DATE a,DATE b){return val[a.ri]-val[a.le-1]<val[b.ri]-val[b.le-1];}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void init(){
	mn[0]=-1;
	for(int i=1;i<=n;i++){
		mn[i]=(!(i&(i-1))) ? mn[i-1]+1 : mn[i-1];
		st[i][0]=i;
	}
	for(int j=1;j<=mn[n];j++)
		for(int i=1;i+(1<<j)-1<=n;i++){
			int a=st[i][j-1],b=st[i+(1<<j-1)][j-1];
			st[i][j]=(val[a]>=val[b] ? a : b);
		}
}
inline int query(int l,int r){
	int k=mn[r-l+1];
	int a=st[l][k],b=st[r-(1<<k)+1][k];
	return val[a]>val[b] ? a : b;
}
int DK(){
	freopen("piano.in","r",stdin);
	freopen("piano.out","w",stdout);
	n=read();k=read();l=read();r=read();
	for(int i=1;i<=n;i++){val[i]=read();val[i]+=val[i-1];}
	init();
	for(int i=1;i+l-1<=n;i++){
		int rig=min(i+r-1,n);
		pq.push((DATE){i,i+l-1,rig,query(i+l-1,rig)});
	}
	for(int i=1;i<=k;i++){
		DATE zhuan=pq.top();pq.pop();
		int mid=zhuan.ri;
		ans+=val[zhuan.ri]-val[zhuan.le-1];
		if(mid>zhuan.fr) pq.push((DATE){zhuan.le,zhuan.fr,mid-1,query(zhuan.fr,mid-1)});
		if(mid<zhuan.to) pq.push((DATE){zhuan.le,mid+1,zhuan.to,query(mid+1,zhuan.to)});
	}
	printf("%lld",ans);
	return 0;
}
int dk=DK();
int main(){
	;
}