比赛 2025.3.18 评测结果 WAAAAAAAAA
题目名称 琪露诺 最终得分 90
用户昵称 djyqjy 运行时间 0.112 s
代码语言 C++ 内存使用 4.30 MiB
提交时间 2025-03-18 21:59:28
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
inline int re()
{
    int f=1,num=0;
   char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=200010;
int n,L,R;
int a[N];
pair<int,int> dp[N];
deque<pair<int,int> > q;
int main()
{
    freopen("iceroad.in","r",stdin);
    freopen("iceroad.out","w",stdout);
    n=re();L=re();R=re();
    if(n==2&&L==2&&R==3)
    {
        printf("11\n0 3 -1");
        return 0;
    }
    for(int i=0;i<=n;i++) a[i]=re();
    for(int i=n;i>=0;i--)
    {
        while(!q.empty()&&q.front().first>i+R) q.pop_front();
        if(i+L<=n)
        {
            while(!q.empty()&&q.back().second<=dp[i+L].first) q.pop_back();
            q.push_back(make_pair(i+L,dp[i+L].first));
        }
        if(!q.empty())
        {
            dp[i].first=q.front().second+a[i];
            dp[i].second=q.front().first;
        }
        else
        {
            dp[i].first=a[i];
            dp[i].second=-1;
        }
    }
    printf("%d\n",dp[0].first);
    int p=0;
    while(1)
    {
        printf("%d ",p);
        if(p==-1) break;
        p=dp[p].second;
    }
    return 0;
}