E45 单调队列优化DP 绿色通道

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
template<typename T>void read(T& x)
{
    x=0;int f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(; isdigit(c);c=getchar()) x=x*10+c-48;
    x=x*f;
}

int n, t, a[N], f[N], q[N];
bool check(int L)
{
    memset(f, 0, sizeof(f));
    memset(q, 0, sizeof(q));
    int l=1, r=1;q[1]=0;
    for(int i=1;i<=n;i++)
    {
        while (l<=r&&q[l]<i-L)l++;
        f[i]=f[q[l]]+a[i];
        while (l<=r&&f[q[r]]>=f[i])r--;
        q[++r]=i;
    }
    for(int i=n-L;i<=n;i++)if(f[i]<=t)return 1;
    return 0;
}
int main()
{
    read(n);read(t);
    for(int i=1;i<=n;i++)read(a[i]);

    int L=0, R=n, ans=-1;
    while(L<=R)
    {
        int mid=(L+R)/2;
        if(check(mid))R=mid-1;ans=mid;
        else L=mid+1;
    }
    printf("%d\n", ans-1);
    return 0;
}