WA subtask,求调(悬一关)

P1725 琪露诺

_std_O2 @ 2024-10-19 09:16:56

#include<bits/stdc++.h>

using namespace std;
const int N=2e6+5;
struct Btree{
    int ls,rs,data;
}tr[N*4+5];

int a[N],dp[N];

void build(int p,int l,int r){
    tr[p].ls=l,tr[p].rs=r;
    if(l==r){
        tr[p].data=-(1<<29);
        return;
    }
    int mid=l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tr[p].data = max(tr[p*2].data , tr[p*2+1].data); 
}

int ask(int p,int l,int r){
    if(l<=tr[p].ls && r>=tr[p].rs) return tr[p].data;

    int mid=(tr[p].ls + tr[p].rs) >> 1;
    int val=-(1<<30);
    if(l<=mid) val = max(ask(p*2,l,r),val);
    if(r>mid) val  = max(ask(p*2+1,l,r),val);
    return val;
} 
void cg(int p,int x,int v){
    if(tr[p].ls==tr[p].rs) {
        tr[p].data=v;
        return;
    }
    int mid=(tr[p].ls + tr[p].rs) >> 1;
    if(x<=mid) cg(p*2,x,v);
    else cg(p*2+1,x,v);
    tr[p].data=max(tr[p*2].data , tr[p*2+1].data);
}
int main(){

    int ans=-(1<<30);
    int n,L,R,m;
    cin>>n>>L>>R;
    for(int i=1;i<=n+1;i++) cin>>a[i];
    build(1,1,n+R);
    for(int i=1;i<=L+1;i++){
        dp[i]=min(a[i],0);//问题出在这行,应该怎么改? 
        cg(1,i,dp[i]);
    }
    for(int i=L+2;i<=n+R;i++){
        int l=i-R,r=i-L;
        int maxn=ask(1,l,r);
        dp[i]=maxn+a[i];
        cg(1,i,dp[i]);
    }
    for(int i=n+1;i<=n+R;i++) ans=max(ans,dp[i]);
    cout<<ans;
}

|