《思远高考绿色通道》(Green Passage, GP)是唐山一中常用的练习册之一，其题量之大深受lsz等许多oiers的痛恨，其中又以数学绿色通道为最。2007年某月某日，soon-if (数学课代表)，又一次宣布收这本作业，而lsz还一点也没有写……

高二数学《绿色通道》总共有n道题目要写(其实是抄)，编号1..n，抄每道题所花时间不一样，抄第i题要花a[i]分钟。由于lsz还要准备NOIP，显然不能成天写绿色通道。lsz决定只用不超过t分钟时间抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。一段连续的空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒。马老师发怒的程度(简称发怒度)等于最长的空题段长度。

现在，lsz想知道他在这t分钟内写哪些题，才能够尽量降低马老师的发怒度。由于lsz很聪明，你只要告诉他发怒度的数值就可以了，不需输出方案。(快乐融化：那么lsz怎么不自己写程序？lsz：我还在抄别的科目的作业……)

第一行为两个整数n,t，代表共有n道题目，t分钟时间。

以下一行，为n个整数，依次为a[1], a[2],... a[n]，意义如上所述。

仅一行，一个整数w，为最低的发怒度。

17 11

6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5

3

60%数据 n<=2000

100%数据 0<n<=50000，0<a[i]<=3000，0<t<=100000000

暴力74分

测试点#gp1.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp10.in  结果:AC    内存使用量:  492kB     时间使用量:  4ms     
测试点#gp11.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp12.in  结果:AC    内存使用量:  492kB     时间使用量:  1ms     
测试点#gp13.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp14.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp15.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp16.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp17.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp18.in  结果:AC    内存使用量:  492kB     时间使用量:  4ms     
测试点#gp19.in  结果:AC    内存使用量:  360kB     时间使用量:  1ms     
测试点#gp2.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp20.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp21.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp22.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp23.in  结果:AC    内存使用量:  492kB     时间使用量:  4ms     
测试点#gp24.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp25.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp26.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp27.in  结果:AC    内存使用量:  488kB     时间使用量:  1ms     
测试点#gp28.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp29.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp3.in  结果:AC    内存使用量:  492kB     时间使用量:  3ms     
测试点#gp30.in  结果:AC    内存使用量:  488kB     时间使用量:  4ms     
测试点#gp31.in  结果:AC    内存使用量:  488kB     时间使用量:  27ms     
测试点#gp32.in  结果:AC    内存使用量:  492kB     时间使用量:  763ms     
测试点#gp33.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp34.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp35.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp36.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp37.in  结果:AC    内存使用量:  364kB     时间使用量:  503ms     
测试点#gp38.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp39.in  结果:AC    内存使用量:  492kB     时间使用量:  19ms     
测试点#gp4.in  结果:AC    内存使用量:  492kB     时间使用量:  4ms     
测试点#gp40.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp41.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp42.in  结果:AC    内存使用量:  492kB     时间使用量:  382ms     
测试点#gp43.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp44.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp45.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp46.in  结果:AC    内存使用量:  492kB     时间使用量:  322ms     
测试点#gp47.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp48.in  结果:TLE    内存使用量:  620kB     时间使用量:  1000ms     
测试点#gp49.in  结果:TLE    内存使用量:  616kB     时间使用量:  1000ms     
测试点#gp5.in  结果:AC    内存使用量:  488kB     时间使用量:  1ms     
测试点#gp50.in  结果:AC    内存使用量:  492kB     时间使用量:  826ms     
测试点#gp6.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     
测试点#gp7.in  结果:AC    内存使用量:  492kB     时间使用量:  6ms     
测试点#gp8.in  结果:AC    内存使用量:  492kB     时间使用量:  0ms     
测试点#gp9.in  结果:AC    内存使用量:  488kB     时间使用量:  0ms     

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 50001

using namespace std;

int n,t,ans;

int f[maxn],a[maxn];

bool check(int mid)

{

    memset(f,/,sizeof f);

    f[]=;

    for(int i=;i<=n;i++)

      for(int j=max(i-mid-,);j<i;j++)

        f[i]=min(f[i],f[j]+a[i]);

    ans=0x3f3f3f3f;

    for(int i=n-mid-;i<=n;i++)

        ans=min(ans,f[i]);

    return ans<=t;

}

int main()

{

    scanf("%d%d",&n,&t);

    for(int i=;i<=n;i++)

      scanf("%d",&a[i]);

    int l=,r=n;

    while(l<r)

    {

        int mid=(l+r)>>;

        if(check(mid))

          r=mid;

        else l=mid+;

    }

    printf("%d\n",l);

    return ;

}

AC

/*用f[i]表示在做第i道题的情况下，前i道题在合法状况下（即空题段长度不超过mid）

可能的所有方案中的最小时间

那么转移方程为 f[i]=min(f[j])+a[i];

其中j的范围是i-mid-1<=j<=i-1

这是因为我们保证a[i]入选，且由于最大空时段为mid

枚举j应当从i之前不做mid个的前面那一道题开始

由于每个f[j]内的状态必然是合法的最小值，

也就是最长空时段不超过mid的最小值，而j又一定被选中（做这道题），最终方案也一定是合法的。

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 50010

using namespace std;

int n,m,ans,t;

int a[maxn],f[maxn],q[maxn];

bool check(int mid)

{

    memset(f,/,sizeof f);

    f[]=;

    int l=,r=;

    q[r++]=;

    for(int i=;i<=n;i++)

    {

        while(l<=r&&q[l]<i-mid-) l++;//删除队列头部所有位置小于查询起始位置的数字

        f[i]=f[q[l]]+a[i];//查询修改后的头元素（最小元素）

        while(l<=r&&f[q[r]]>=f[i]) r--;//删除队列尾部所有耗时比当前元素大的元素

        q[++r]=i;

    }

    /*

        等价于f[i]=最小的f[j]+a[i];

        i跟j之间空着一段mid 所以j就是i-mid-1

    */

    int ans=0x3f3f3f3f;

    for(int i=n-mid-;i<=n;i++)

        ans=min(ans,f[i]);

    return ans<=t;

}

int main()

{

    scanf("%d%d",&n,&t);

    for (int i=;i<=n;i++)

      scanf("%d",&a[i]);

    int l=,r=n;

    while(l<r)

    {

        int mid=(l+r)>>;

        if(check(mid))

          r=mid;

        else l=mid+;

    }

    printf("%d\n",l);

    return ;

}