记录编号	305187	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	3.909 s
提交时间	2016-09-10 17:04:18	内存使用	79.24 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#define maxn 1000000
using namespace std;
typedef long long ll;
class poi{
public:
	int x,l,r;
	ll val;
	bool operator () (poi a,poi b){
		return a.val<b.val;
	}
};
int n,k,l,r;
ll sum[maxn]={0};
int a[maxn];
int st[maxn][20];
int minv(int l,int r){
	if (sum[l]<sum[r]) return l;
	else return r;
}
void rmq(){
	for (int i=0;i<=n;i++){
		st[i][0]=i;
	}
	for (int i=1;(1<<i)<=n;i++){
		for (int j=0;(j+(1<<i)-1)<=n;j++){
			st[j][i]=minv(st[j][i-1],st[j+(1<<i-1)][i-1]);
		}
	}
}
int query(int l,int r){
	int t=1+log2(r-l+1),ans;
	if ((r-l+1)<(1<<t)) t--;
	ans=minv(st[l][t],st[r-(1<<t)+1][t]);
	return ans;
}

priority_queue<poi,vector<poi>,poi> pq; 
void read(){
	scanf("%d%d%d%d",&n,&k,&l,&r);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	rmq();
	for (int i=l;i<=n;i++){
		poi p;
		p.r=i-l; p.l=max(0,i-r); p.x=i;
		p.val=sum[p.x]-sum[query(p.l,p.r)];
//		printf("%d %d %d %d\n",p.x,p.l,p.r,p.val);
		pq.push(p);
	}
	int tot=0;
	ll ans=0;
	while (tot<k){
		poi p=pq.top(),a;
		pq.pop();
		int t=query(p.l,p.r);
		if (p.l<=t-1) {
			a.l=p.l;
			a.r=t-1;
			a.x=p.x;
			a.val=sum[a.x]-sum[query(a.l,a.r)];
			pq.push(a);
		}
		if (p.r>=t+1) {
			a.l=t+1;
			a.r=p.r;
			a.x=p.x;
			a.val=sum[a.x]-sum[query(a.l,a.r)];
			pq.push(a);
		}
		ans+=p.val;
		tot++;
	}
	printf("%lld",ans);
}

int main(){
	freopen("piano.in","r",stdin);
	freopen("piano.out","w",stdout);
	read();
	return 0;
}