比赛 |
东方幻想乡 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);
}