61求调 双指针+单调队

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e6+5;
int n,p,d,w[N],l=1,r=1,s[N],t[N],ans;
deque<int> q;
signed main(){
	cin>>n>>p>>d;
	for(int i=1;i<=n;i++){
		cin>>w[i];
		s[i]=s[i-1]+w[i];
		if(s[i]<=p) r=i;
	}
	ans=r;
	for(int i=1;i<=n-d+1;i++) t[i]=s[i+d-1]-s[i-1];
	for(int i=1;i<=r-d+1;i++){
		while(!q.empty()&&t[i]>t[q.back()]) q.pop_back();
		q.push_back(i);
	}
	for(int i=r;i<=n;i++){
		if(i-l+1<d){
			if(s[i]-s[l-1]>p) l++;
			else ans=max(ans,i-l+1);
			continue;
		}
		while(!q.empty()&&t[i-d+1]>t[q.back()]) q.pop_back();
		q.push_back(i-d+1);
		while(!q.empty()&&q.front()<l||q.front()+d-1>i) q.pop_front();
		if(s[i]-s[l-1]-t[q.front()]<=p) ans=max(ans,i-l+1);
		else l++;
	}
	cout<<ans;
	return 0;
}