SubstackWA
查看原帖
SubstackWA
554729
1304csnapdragon楼主2023/2/26 11:30
#include<bits/stdc++.h>
using namespace std;
long n,l,r,head=0,tail=0,q[200006],a[200006],dp[200006];
int main() {
	for(int i=1; i<=n; i++) {
		dp[i]=-2e9;
	}
	dp[0]=0;
	scanf("%ld%ld%ld",&n,&l,&r);
	for(int i=0; i<=n; i++) {
		cin>>a[i];
		q[i]=a[i];
	}
	long ans=-2e9;
	for (int i=l; i<=n; i++) {
		while (head<=tail&&q[head]<i-(r)) head++;
		while (head<=tail&&dp[q[tail]]<=dp[i-l])
			tail--;
		q[++tail]=i-l;
		dp[i]=max(dp[i],dp[q[head]]+a[i]);
		if(i+r>n) ans=max(ans,dp[i]) ;
	}
	printf("%ld",ans);
	return 0;
}

…… QwQ

2023/2/26 11:30
加载中...