记录编号	425526	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	1.088 s
提交时间	2017-07-15 11:57:18	内存使用	42.28 MiB

#define MAXN 500005
#include <bits/stdc++.h>
typedef long long ll;
int n,k,L,R,w[MAXN][21],s[MAXN],bit[21];
ll Ans;

struct pa{
    int pos,l,r,now;
    bool operator < (const pa&a)const{
        return s[now]-s[pos-1]<s[a.now]-s[a.pos-1];
    }
};
std::priority_queue<pa>q;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+(ch^48);
    return x*f;
}

inline int query(int l,int r){
    int k=0;
    while((1<<(k+1))<=r-l+1)k++;
    int x1=w[l][k],x2=w[r-bit[k]+1][k];
    return s[x1]>s[x2]?x1:x2;
}

int main(){
    freopen("piano.in","r",stdin);
    freopen("piano.out","w",stdout);
    n=read();k=read();L=read();R=read();bit[0]=1;
    for(int i=1;i<=n;i++)s[i]=s[i-1]+read();
    for(int i=1;i<=n;i++)w[i][0]=i;
    for(int i=1;i<=20;i++)bit[i]=bit[i-1]<<1;
    for(int i=1;bit[i]<=n;i++)
        for(int j=1;j<=n-bit[i]+1;j++){
            int x1=w[j][i-1],x2=w[j+bit[i-1]][i-1];
            w[j][i]=s[x1]>s[x2]?x1:x2;
        }
    for(int i=1;i<=n-L+1;i++){
        int l=i+L-1,r=std::min(i+R-1,n);
        int now = query(l,r);
        q.push((pa){i,l,r,now});
    }
    for(int i=1;i<=k;i++){
        pa lc = q.top();q.pop();
        Ans += s[lc.now]-s[lc.pos-1];
        if(lc.now+1<=lc.r)q.push((pa){lc.pos,lc.now+1,lc.r,query(lc.now+1,lc.r)});
        if(lc.now-1>=lc.l)q.push((pa){lc.pos,lc.l,lc.now-1,query(lc.l,lc.now-1)});
    }
    printf("%lld\n",Ans);
}