记录编号	239516	评测结果	AAAAAAAAAA
题目名称	[東方S1] 琪露诺	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2016-03-20 11:57:40	内存使用	4.10 MiB

#include<cstdio>
const int maxn=200005;
int a[maxn],f[maxn],pre[maxn];
int read(){
	bool minus=false;
	char ch;int x;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if(ch=='-'){
		minus=true;
		ch=getchar();
	}
	x=ch-'0';
	while(ch=getchar(),ch<='9'&&ch>='0')x=x*10+ch-48;
	return minus?-x:x;
}
int k;
struct queue{
	int q[maxn],index[maxn];
	int head,tail;
	void add(int x,int i){
		int lim=i+1-k;
		while(head<tail&&index[head]<lim)head++;
		while(head<tail&&q[tail-1]<=x)tail--;
		index[tail]=i;
		q[tail++]=x;
	}
	int max(){
		return q[head];
	}
}q1;
void output(int x){
	if(x==pre[x])printf("%d",x);
	else{
		output(pre[x]);
		printf(" %d",x);
	}
}
int main(){
	freopen("iceroad.in","r",stdin);
	freopen("iceroad.out","w",stdout);
	int n=read(),l=read(),r=read();
	k=r+1-l;
	q1.add(0,0);
	for(int i=0;i<=n;++i)a[i]=read();
	for(int i=l;i<=n;++i){
		if(i-l>0)q1.add(f[i-l],i-l);
		f[i]=a[i]+q1.max();
		pre[i]=q1.index[q1.head];
		if(pre[i]<l)pre[i]=0;
	}
	int lim=n+r,tmp,last=n+1;	
	for(int i=n;i<=lim;++i){
		if(i-l>0)q1.add(f[i-l],i-l);
		tmp=q1.max();
		if(tmp>f[last])last=q1.index[q1.head];
		
	}
	printf("%d\n",f[last]);
	output(last);
	printf(" -1\n");
	fclose(stdin);fclose(stdout);
	return 0;
}