题解 P3594 【[POI2015]WIL-Wilcze doły】

双指针+单调队列
先使用双指针卡出区间，用单调队列进行类似滑动窗口的方式维护定长区间和最小值即可
时间复杂度$O(n)$

#include<iostream>
#include<queue> 
#define int long long
using namespace std;
int a[2000005],pre[2000005];
deque<int> q;
signed main(){
	int p,n,d;
	cin>>n>>p>>d;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pre[i]=pre[i-1]+a[i];
	}
	int l=1;
	q.push_back(d);
	int ans=d;
	for(int r=d+1;r<=n;r++){
		while(!q.empty()&&pre[q.back()]-pre[q.back()-d]<pre[r]-pre[r-d])q.pop_back();
		q.push_back(r);
		while(!q.empty()&&pre[r]-pre[l-1]-pre[q.front()]+pre[q.front()-d]>p){
			l++;
			while(!q.empty()&&q.front()-d+1<l)q.pop_front();
		}
		ans=max(ans,r-l+1);
	}
	cout<<ans;
	return 0;
}