题目传送门

record1

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
priority_queue<pii> q;
int main(){
	int n,l,r;
	cin>>n>>l>>r;
	long long arr[n+1],f[n+1];
	for(int i=0;i<=n;i++){
		cin>>arr[i];
		f[i]=0;
	}
	arr[0]=0;
	f[0]=0;
	q.push(make_pair(0,0));
	for(int i=1;i<=n;i++){
		int L=i-r,R=i-l;
		queue<pii> q1; 
		int flag=2;
		while(!q.empty()&&(q.top().second<L||q.top().second>R)){
			if(q.top().second<L)q.pop();
			else {q1.push(q.top());q.pop();}
		}
		if(!q.empty()){
			f[i]=q.top().first+arr[i];
			q.push(make_pair(f[i],i));
		}
		while(!q1.empty()){q.push(q1.front());q1.pop();}
	}
	long long ans=0;
	for(int i=n;i>n-r;i--){
		ans=max(ans,f[i]);
	}
	cout<<ans;
	return 0;
}

record2

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
priority_queue<pii> q;
int main(){
	int n,l,r;
	cin>>n>>l>>r;
	long long arr[n+1],f[n+1],st[n+1];
	for(int i=0;i<=n;i++){
		cin>>arr[i];
		f[i]=0;
		st[i]=1;
	}
	st[0]=1;
	arr[0]=0;
	f[0]=0;
	q.push(make_pair(0,0));
	for(int i=1;i<=n;i++){
		int L=i-r,R=i-l;
		queue<pii> q1; 
		int flag=2;
		while(!q.empty()&&(q.top().second<L||q.top().second>R)){
			if(q.top().second<L)q.pop();
			else {q1.push(q.top());q.pop();}
		}
		if(!q.empty()){
			f[i]=q.top().first+arr[i];
			q.push(make_pair(f[i],i));
		}
		else{
			st[i]=0;
		}
		while(!q1.empty()){q.push(q1.front());q1.pop();}
	}
	long long ans=-1e9;
	for(int i=n;i>n-r;i--){
		if(st[i])
		ans=max(ans,f[i]);
	}
	cout<<ans;
	return 0;
}