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

/*
 *Problem  : iceroad
 *Contest  : Touhou Stage.1
 *Author   : Yee-fan Zhu
 *Gmail    : zyfworks@gmail.com
 *Solution : DP / STL set
 */
#include <cstdlib>
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
const int INF=~0u>>2;
const int MAXN=200010*2;
int N,L,R,Num[MAXN],F[MAXN],path[MAXN];
multiset<int> heap;
int Maxp,Maxn=0;

class Deque
{
public:int val,pos;
};
class cmp
{
public:
	bool operator() (const Deque&a,const Deque&b)
	{
		if(a.val!=b.val) return a.val<b.val;
		return a.pos<b.pos;
	}
};
set<Deque,cmp> deque;
 
inline void init()
{
	scanf("%d %d %d\n",&N,&L,&R);
	for(int i=0;i<=N;i++)
	{
		scanf("%d",&Num[i]);
		F[i]=-INF;
	}
	for(int i=N+1;i<=N+R;i++)
		F[i]=-INF;
	F[0]=Num[0];
}
 
inline void dp()
{
	int tmp;
	Deque dmp;
	set<Deque,cmp> :: iterator diter;
	multiset<int> :: iterator iter;
	 
	for(int i=1;i<=N+R;i++)
	{
		if(i-R-1>=0) 
		{ 
			//heap.erase(F[i-R-1]);
			dmp=(Deque){F[i-R-1],i-R-1};
			deque.erase(dmp);
		}
		if(i-L>=0) 
			if(F[i-L]!=-INF)
				{
					//heap.insert(F[i-L]);
					dmp=(Deque){F[i-L],i-L};
					deque.insert(dmp);
				}
		//if(heap.size()==0) continue;
		if(deque.size()==0) continue;
		/*
		iter=heap.end(); iter--;
		tmp=*iter;
		F[i]=tmp+Num[i];*/
		diter=deque.end(); diter--;
		tmp=diter->val; F[i]=tmp+Num[i];
		tmp=diter->pos; path[i]=tmp;
	}
	//printf("%d\n",*max_element(F+2+N,F+N+R+1));
}

inline void output()
{
	int michi[MAXN]={0},top=0;
	for(int i=N+1;i<=N+R;i++)
	{
		if(F[i]<=Maxn) continue;
		Maxn=F[i]; Maxp=i;
	}
	printf("%d\n",Maxn);
	//printf("%d\n",Maxp);
	int tmp=path[Maxp];
	while(tmp)
	{
		michi[++top]=tmp;
		tmp=path[tmp];
	}
	printf("0 ");
	for(int i=top;i>=1;i--)
		printf("%d ",michi[i]);
	printf("-1\n");
}

int main()
{
	//freopen("in","r",stdin);
	freopen("iceroad.in","r",stdin);
	freopen("iceroad.out","w",stdout);
	init();
	dp();
	output();
	return 0;
}