记录编号	389047	评测结果	AAAAAAAAAA
题目名称	[東方S1] 琪露诺	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.438 s
提交时间	2017-03-30 15:05:03	内存使用	5.65 MiB

#include <cstdio>
#include <cstdarg>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <cctype>
using namespace std;
struct node{
  int maxv, pos;
  node *ls, *rs;
  node(){ls = rs = NULL, maxv = -0x7fffffff;}
  void pushup(){
    maxv = -0x7fffffff;
    if(ls && ls->maxv > maxv){
      maxv = ls->maxv; pos = ls->pos;
    }
    if(rs && rs->maxv > maxv){
      maxv = rs->maxv; pos = rs->pos;
    }
  }
};
template<typename T>
void splay(T &r){
  char c; bool s = false;
  while((c = getchar())){
    if(c >= '0' && c <= '9'){
      r = c^0x30; break;
    }else if(c == '-')s = true;
  }
  while(isdigit(c = getchar()))r = r*10+(c^0x30);
  if(s)r = -r;
}
node *root;
node *build(int l, int r){
  if(l > r)return NULL;
  node *d = new node();
  if(l == r)d->pos = l;
  else if(l < r){
    int m = (l+r)>>1;
    d->ls = build(l, m); d->rs = build(m+1, r);
  }
  return d;
}
void modify(node *x, int p, int v, int L, int R){
  if(!x)return;
  if(L == R && p == L){
    x->maxv = v;
    return;
  }
  int M = (L+R)>>1;
  if(p <= M)modify(x->ls, p, v, L, M);
  else if(p > M)modify(x->rs, p, v, M+1, R);
  x->pushup();
}
int lastmax, lastpos;
void query(node *x, int l, int r, int L, int R){
  if(!x)return;
  if(l <= L && R <= r){
    if(x->maxv > lastmax){
      lastmax = x->maxv;
      lastpos = x->pos;
    }
  }
  else{
    int M = (L+R)>>1;
    if(l <= M)query(x->ls, l, r, L, M);
    if(r > M)query(x->rs, l, r, M+1, R);
  }
}
const int MAXN = 200003;
int ice[MAXN<<1];
int f[MAXN<<1];
int p[MAXN<<1];
int ans[MAXN];
int main(){
  freopen("iceroad.in", "r", stdin);
  freopen("iceroad.out", "w", stdout);
  int n, L, R;
  splay(n); splay(L); splay(R);
  root = build(0, n+R);
  for(int i = 0; i <= n; i++)splay(ice[i]);
  for(int i = 0; i <= n+R; i++){
    int l = i-R;
    int r = i-L;
    if(r < 0){
      modify(root, i, 0, 0, n+R);
      continue;
    }
    l = max(0, l);
    r = min(r, n);
    if(l > r)continue;
    lastmax = -0x7fffffff;
    query(root, l, r, 0, n+R);
    f[i] = lastmax+ice[i];
    p[i] = lastpos;
    modify(root, i, f[i], 0, n+R);
  }
  lastmax = -0x7fffffff;
  query(root, n+1, n+R, 0, n+R);
  printf("%d\n", lastmax);
  int pans = 0;
  ans[pans++] = -1;
  int k = lastpos;
  while(p[k]){
    k = p[k];
    if(k <= n)ans[pans++] = k;
  }ans[pans++] = 0;
  for(int i = pans-1; ~i; i--)printf("%d ", ans[i]);
  return 0;
}