记录编号	41664	评测结果	AAAAAAAAAA
题目名称	[東方S1] 琪露诺	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.155 s
提交时间	2012-08-07 21:54:21	内存使用	7.92 MiB

#include <cstdio>
using namespace std;

const int minnum=-1000000000;

int a[400002],f[400002],pos[400002],val[400002],rec[400002]={-1};

void printway(int pos)
{
	if (pos!=0)
	{
		printway(rec[pos]);
		printf("%d ",rec[pos]);
	}
}

int main(void)
{
	freopen("iceroad.in","r",stdin);
	freopen("iceroad.out","w",stdout);
	int i,n,l,r,head=-1,tail=0,maxnum,maxpos;
	scanf("%d%d%d",&n,&l,&r);
	for (i=0;i<=n;i++)
		scanf("%d",&a[i]);
	if (pos[tail]==i+1-r)
		tail++;
	if (1-l>=0)
	{
		pos[++head]=1-l;
		val[head]=f[1-l];
	}
	for (i=1;i<=n+l;i++)
	{
		if (head<tail)
		{
			f[i]=minnum;
			rec[i]=-1;
		}
		else
		{
			f[i]=val[tail]+a[i];
			rec[i]=pos[tail];
		}
		if (pos[tail]==i-r)
			tail++;
		if (i+1-l>=0)
		{
			pos[++head]=i+1-l;
			val[head]=f[i+1-l];
			while (head>tail&&val[head-1]<=val[head])
			{
				val[head-1]=val[head];
				pos[head-1]=pos[head];
				head--;
			}
		}
	}
	maxnum=minnum;
	for (i=n+1;i<=n+l;i++)
		if (maxnum<f[i])
		{
			maxnum=f[i];
			maxpos=i;
		}
	printf("%d\n",maxnum);
	printway(maxpos);
	printf("-1\n");
	return(0);
}