P3594,正解是单调队列,想用双指针+堆卡过去没成功。
#include<bits/stdc++.h>
#define int long long
#define N 2000005
using namespace std;
int n,m,d,a[N],s[N],ans;
priority_queue<int>q;
map<int,int>mp;
signed main(){
ios::sync_with_stdio(false);
read(n),read(m),read(d);
for(int i=1;i<=n;i++) read(a[i]),s[i]=s[i-1]+a[i];
for(int l=1,r=d;r<=n;r++){
q.push(s[r]-s[r-d]),mp[s[r]-s[r-d]]++;
while(true){
while(!mp[q.top()]) q.pop();
if(s[r]-s[l-1]-q.top()>m) l++,mp[s[l+d-1]-s[l-1]]--;
else break;
}
ans=max(ans,r-l+1);
}
write(ans);
return 0;
}