比赛 东方幻想乡 S1 评测结果 AWWWWWWWWW
题目名称 琪露诺 最终得分 10
用户昵称 Truth.Cirno 运行时间 0.159 s
代码语言 C++ 内存使用 4.10 MiB
提交时间 2012-08-07 20:31:08
显示代码纯文本
#include <cstdio>
using namespace std;

const int minnum=-1000000000;

int a[200002],f[200002],pos[200002],val[200002],rec[200002]={-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;
	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;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--;
			}
		}
	}
	f[i]=val[tail];
	rec[i]=pos[tail];
	printf("%d\n",f[n+1]);
	printway(n+1);
	printf("-1\n");
	return(0);
}