记录编号	393003	评测结果	AAAAAAAAAA
题目名称	[東方S1] 琪露诺	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.431 s
提交时间	2017-04-09 18:12:26	内存使用	15.58 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 2e5 + 10;

const inline int in(void){
	char tmp = getchar();
	int res = 0, f = 1;
	while(!isdigit(tmp) && tmp != '-')tmp = getchar();
	if(tmp == '-')f = -1, tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res * f;
}

template<typename T>
T my_max(const T& a, const T& b){
	if(a < b)return b;
	return a;
}

struct DATA{
	int val, w;
	
	DATA(){;}
	DATA(int _val, int _w){
		val = _val, w = _w;
	}
	
	bool operator < (const DATA& a)const{
		return val < a.val;
	}
};

struct NODE{
	DATA val;
	NODE *ls, *rs;
	NODE *fa;
	
	NODE(){
		ls = rs = fa = NULL;
	}
};

inline NODE *new_node(void){
	static NODE ns[MAXN * 3];
	static int tot = 0;
	return ns + tot++;
}

NODE *Build(NODE *father, int l, int r);
DATA Query(NODE *now, int l, int r, int L, int R);
void updata(NODE *now, int w);
void print_road(void);

int N, L, R;
int a[MAXN], f[MAXN];
int pre[MAXN];
NODE *root, *father[MAXN];
int Stack[MAXN], top;

int main(){
#ifndef LOCAL
	freopen("iceroad.in", "r", stdin);
	freopen("iceroad.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif

	N = in(), L = in(), R = in();
	
	for(int i = 0; i <= N; ++i)a[i] = in();
	
	root = Build(NULL, 0, N);
	
	DATA tmp;
	
	for(int i = L; i < R; ++i){
		tmp = Query(root, 0, i - L, 0, N);
		if(tmp.w < L){
			f[i] = a[i];
			pre[i] = 0;
		}
		else{
			f[i] = tmp.val + a[i];
			pre[i] = tmp.w;
		}
		updata(father[i], f[i]);
	}
	
	for(int i = R; i <= N; ++i){
		tmp = Query(root, i - R, i - L, 0, N);
		f[i] = tmp.val + a[i];
		pre[i] = tmp.w;
		updata(father[i], f[i]);
	}
	
	tmp = Query(root, N + 1 - R, N, 0, N);
	f[N + 1] = tmp.val;
	pre[N + 1] = tmp.w;
	
	printf("%d\n", f[N + 1]);
	
#ifdef debug
	printf("%d %d %d\n", N, L, R);
	for(int i = 0; i <= N + 1; ++i){
		printf("%d:%d ", i, a[i]);
	}
	putchar('\n');
	for(int i = 0; i <= N + 1; ++i){
		printf("%d:%d ", i, f[i]);
	}
#endif
	
	print_road();
	
	return 0;
}

NODE *Build(NODE *fath, int l, int r){
	NODE *p = new_node();
	p->fa = fath;
	if(l == r){
		p->val = DATA(f[l], l);
		father[l] = p;
	}
	else{
		int mid = (l + r) >> 1;
		p->ls = Build(p, l, mid);
		p->rs = Build(p, mid + 1, r);
		p->val = my_max(p->ls->val, p->rs->val);
	}
	return p;
}

DATA Query(NODE *now, int l, int r, int L, int R){
	if(l == L && r == R)return now->val;
	int mid = (L + R) >> 1;
	if(r <= mid) return Query(now->ls, l, r, L, mid);
	if(mid < l) return Query(now->rs, l, r, mid + 1, R);
	return my_max(Query(now->ls, l, mid, L, mid), Query(now->rs, mid + 1, r, mid + 1, R));
}

void updata(NODE *now, int w){
	DATA& tmp = now->val;
	tmp.val = w;
	while((now = now->fa) && now->val < tmp){
		now->val = tmp;
	}
	return ;
}

void print_road(void){
	Stack[top++] = -1;
	
	int now = N + 1;
	while(now){
		Stack[top++] = pre[now];
		now = pre[now];
	}
	
	while(top){
		printf("%d ", Stack[--top]);
	}

	return ;
}