记录编号	115616	评测结果	AAAAAAAAAA
题目名称	[東方S1] 琪露诺	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.103 s
提交时间	2014-08-21 20:37:23	内存使用	2.79 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct node
{
  int pos,value;
  node (int p,int v):pos(p),value(v){};
};
//==============var declaration=================
deque <node> Q;
//Q.front is the max value
int prev[200010];
int cold[200010];
int f[200010];
bool vis[200010];
//==============function declaration============
void printpath(int x);
//==============main code=======================
int main()
{  
  string FileName="iceroad";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
#endif   
  int n,l,r;
  scanf("%d%d%d",&n,&l,&r);
  For(i,0,n)
    scanf("%d",&cold[i]);
  memset(vis,0,sizeof(vis));
  memset(prev,-1,sizeof (prev));
  Q.push_back(node(0,cold[0]));
  int maxc=-INF;
  int maxn;
  For(i,l,n)
  {
    if (!Q.empty()&&Q.front().pos<i-r)
      Q.pop_front();
    if (i-l>0)
    {  
      while ((!Q.empty())&&f[i-l]>Q.back().value)
        Q.pop_back();
      Q.push_back(node(i-l,f[i-l]));
    }
    prev[i]=Q.front().pos;
    f[i]=Q.front().value+cold[i];
    if (f[i]>maxc)
    {
      maxc=f[i];
      maxn=i;
    }
  }
  printf("%d\n",maxc);
  printpath(maxn);
  printf("-1\n");
  return 0;
}
//================fuction code====================
void printpath(int x)
{
  if (prev[x]!=-1)
    printpath(prev[x]);
  printf("%d ",x);
}