WA subtask,求调(悬一关)
  • 板块P1725 琪露诺
  • 楼主_std_O2
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/19 09:16
  • 上次更新2024/10/19 11:16:42
查看原帖
WA subtask,求调(悬一关)
1273684
_std_O2楼主2024/10/19 09:16
#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;
}

2024/10/19 09:16
加载中...