WA on Sub2 求调

P1725 琪露诺

张伟大律师 @ 2024-11-25 20:05:01

#include<bits/stdc++.h>
#define int long long
#define MAXN 200010
const int INF = 2e9;
using namespace std;
int L,R,N;
int dp[MAXN]={0},a[MAXN],res=-INF;
signed main(){
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;
    cin>>N>>L>>R;
    for(int i=0;i<=N;i++)cin>>a[i];
    deque<int> q;
    for(int i=L;i<=N;i++){
        while(!q.empty() && q.front()+R<i)q.pop_front();//不合法检验
        while(!q.empty() && dp[i-L]>=dp[q.back()])q.pop_back();
        q.push_back(i-L);
        dp[i]=dp[q.front()]+a[i];
        if(i+R>N)res=max(res,dp[i]);
    }
    cout<<res;
    return 0;
}

|