比赛 2025.3.18 评测结果 AAAAAAAAAA
题目名称 琪露诺 最终得分 100
用户昵称 123 运行时间 0.160 s
代码语言 C++ 内存使用 5.03 MiB
提交时间 2025-03-18 19:35:22
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=800010;
int n,l,r,from[N],cnt=0,b[N],tot=0;
long long a[N],ret=0,dp[N];
deque<pair<int,long long>> q;
int main() {
    freopen("iceroad.in","r",stdin);
    freopen("iceroad.out","w",stdout);
    cin>>n>>l>>r;
    for (int i=0;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    from[0]=-1;
    q.push_front({0,0});
    for (int i=l;i<=n+r;i++)
    {
        while (!q.empty() && q.back().first+r<i)
        {
            q.pop_back();
        }
        dp[i]=q.back().second+a[i];
        from[i]=q.back().first;
        while (!q.empty() && q.front().second<dp[i-l+1])
        {
            q.pop_front(); 
        }
        q.push_front({i-l+1,dp[i-l+1]});
    }
    for (int i=n+1;i<=n+r;i++)
    {
        ret=max(ret,dp[i]);
        cnt=i;
    } 
    cout<<ret<<endl;
    for (int i=from[cnt];i>=0;i=from[i])
    {
        b[++tot]=i;
    }
    for (int i=tot;i>1;i--)
    {
        printf("%d ",b[i]);
    }
    printf("-1");
}