记录编号	305405	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	3.912 s
提交时间	2016-09-10 20:24:34	内存使用	38.04 MiB

//KZNS
//Best Wil
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
#define Nmax 500003
int N, K, L, R;
int A[Nmax];
int S[Nmax] = {0};
inline void rin() {
	scanf("%d %d %d %d", &N, &K, &L, &R);
	for (int i = 1; i <= N; i++) {
		scanf("%d", A+i);
		S[i] = S[i-1] + A[i];
	}
}
class poi {
public:
	int s, l, d, r, v;
	bool operator () (const poi a, const poi b){
		return a.v < b.v;
	}
};
inline int loog(const int x) {
	int u = 1;
	for (int i = 0; true; i++)
		if (x < (u<<=1))
			return i;
}
int mx[Nmax][20];
inline int maax(const int a, const int b) {
	if (S[a] < S[b])
		return b;
	return a;
}
void fir() {
	for (int i = 1; i <= N; i++)
		mx[i][0] = i;
	for (int k = 1; (1<<k) <= N; k++)
		for (int i = 1; i+(1<<k)-1 <= N; i++)
			mx[i][k] = maax(mx[i][k-1], mx[i+(1<<k-1)][k-1]);
}
priority_queue<poi, vector<poi>, poi> ls;
void work() {
	int u;
	poi poiu;
	for (int i = 1; i + L-1 <= N; i++) {
		poiu.s = i;
		poiu.l = i+L-1;
		poiu.r = min(i+R-1, N);
		u = loog(poiu.r - poiu.l + 1);
		poiu.d = maax(mx[poiu.l][u], mx[poiu.r-(1<<u)+1][u]);
		poiu.v = S[poiu.d] - S[i-1];
		ls.push(poiu);
	}
	long long ans = 0;
	poi pu;
	while (K--) {
		poiu = ls.top();
		ls.pop();
		ans += poiu.v;
		pu.s = poiu.s;
		if (poiu.d-1 >= poiu.l) {
			pu.l = poiu.l;
			pu.r = poiu.d-1;
			u = loog(pu.r-pu.l+1);
			pu.d = maax(mx[pu.l][u], mx[pu.r-(1<<u)+1][u]);
			pu.v = S[pu.d] - S[pu.s-1];
			ls.push(pu);
		}
		if (poiu.d+1 <= poiu.r) {
			pu.l = poiu.d+1;
			pu.r = poiu.r;
			u = loog(pu.r-pu.l+1);
			pu.d = maax(mx[pu.l][u], mx[pu.r-(1<<u)+1][u]);
			pu.v = S[pu.d] - S[pu.s-1];
			ls.push(pu);
		}
	}
	printf("%lld\n", ans);
}
int main() {
	freopen("piano.in", "r", stdin);
	freopen("piano.out", "w", stdout);
	rin();
	fir();
	work();
	return 0;
}
//All Illu
//UBWH