记录编号	459906	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	123	是否通过	通过
代码语言	C++	运行时间	2.247 s
提交时间	2017-10-16 09:45:39	内存使用	322.31 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <algorithm>
using namespace std;
class qw{
public:
	long long x,L,R,y,z;
};
qw h;
class zky{
public:
	long long ya,yb;
};
zky dp[800100][26]={0};
long long n,m,k,l,r;
priority_queue <qw> q;
long s[600000]={0},f[600000]={0};
bool operator <(qw a,qw b){return a.y<b.y?1:0;}
void hh(int i,int j)
{
	long long k=0,ans;
	while((1<<(k+1))<=j-i+1)
		k++;
	if(dp[i][k].ya>=dp[j-(1<<k)+1][k].ya)
	{
		h.y=dp[i][k].ya;
		h.z=dp[i][k].yb;
	}
	else
	{
		h.y=dp[j-(1<<k)+1][k].ya;
		h.z=dp[j-(1<<k)+1][k].yb;
	}
}
int make(int u,int i,int j,int p){
	if(i<=p-1)
	{
		h.x=u;h.L=i;h.R=p-1;hh(i,p-1);
		h.y=h.y-f[u-1];
		q.push(h);
	}
	if(p+1<=j)
	{
		h.x=u;h.L=p+1;h.R=j;hh(p+1,j);
		h.y=h.y-f[u-1];
		q.push(h);
	}
	return 0;
}
int main(){
	freopen ("piano.in","r",stdin);
	freopen ("piano.out","w",stdout);
	int a,b;
	long long ans=0;
	scanf("%d%d%d%d",&n,&k,&l,&r);
	for(a=1;a<=n;a++)
		scanf("%d",&f[a]);
	for(a=1;a<=n;a++)
		f[a]=f[a-1]+f[a];
	for(a=1;a<=n;a++)
	{
		dp[a][0].ya=f[a];
		dp[a][0].yb=a;
	}
	for(a=1;(1<<a)<=n;a++)
	{
		for(b=1;b+(1<<(a-1))<=n;b++)
		{
			if(dp[b][a-1].ya>dp[b+(1<<(a-1))][a-1].ya)
				dp[b][a]=dp[b][a-1];
			else
				dp[b][a]=dp[b+(1<<(a-1))][a-1];
		}
	}
	for(a=1;a<=n-l+1;a++)
	{
		h.x=a;
		h.L=a+l-1;
		h.R=min(a+r-1,n);
		hh(a+l-1,h.R);
		h.y=h.y-f[a-1];
		q.push(h);
	}
	for(a=1;a<=k;a++)
	{
		h=q.top();
		ans+=h.y;
		q.pop();
		make(h.x,h.L,h.R,h.z);
	}
	printf("%lld",ans);
	return 0;
}