比赛 2025.3.18 评测结果 AAAAAAAAAA
题目名称 琪露诺 最终得分 100
用户昵称 郑霁桓 运行时间 0.317 s
代码语言 C++ 内存使用 6.37 MiB
提交时间 2025-03-18 20:55:05
显示代码纯文本
#include<bits/stdc++.h> 
using namespace std;
priority_queue<pair<long long,long long> >q;
long long n,l,r,a[400005],f[400005],tp,pt,as=-1e17,ps,ft[400005];
vector<long long>v;
int main(){
    freopen("iceroad.in","r",stdin);
    freopen("iceroad.out","w",stdout);
    cin>>n>>l>>r;           
    for(int i=0;i<=n;i++) cin>>a[i];
    q.push({0,0}); 
    for(int i=l;i<=n;i++){
        f[i]=-1e17;
        if(i-l>=l&&f[i-l]!=-1e17) q.push({f[i-l],i-l});
        while(!q.empty()){
            tp=q.top().first,pt=q.top().second;
            if(i<=pt+r){
                f[i]=a[i]+tp,ft[i]=pt;
                break;  
            }else q.pop();
        }
        if(i+r>n&&as<=f[i]) as=f[i],ps=i;
    }
    cout<<as<<"\n0 ",tp=ps;
    while(ft[ps]) ps=ft[ps],v.push_back(ps);
    for(int i=v.size()-1;i>=0;i--) cout<<v[i]<<" ";
    cout<<tp<<" -1";
    return 0;
}