贝茜参加某编程比赛。

比赛一共有 n
道题，编号 1∼n
，其中第 i
题需要她花费 ai
时间方可完成。

贝茜可以自由选择从某一道题开始（前面的题相当于全部放弃），按编号顺序依次答题，每完成一题才会作答下一题，直到完成最后一题或比赛时间结束为止。

本次比赛的持续时间为 t
，请你计算贝茜最多可以完成多少题。

输入格式
第一行包含整数 n,t
。

第二行包含 n
个整数 a1,a2,…,an
。

输出格式
一个整数，表示最多可以完成的题目数量。

数据范围
前 6
个测试点满足 1≤n≤6
。
所有测试点满足 1≤n≤105
，1≤t≤109
，1≤ai≤104
。

输入样例1：
4 5
3 1 2 1
输出样例1：
3
输入样例2：
3 3
2 2 3
输出样例2：
1

二分+前缀和

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 100010;
int a[N];
LL n,t;
LL sum[N];

//mid为能做的题数
bool check(int mid)
{
    //枚举大小为mid的区间
    for(int i = mid; i <= n; i++)
    {
        LL total_time = sum[i] - sum[i - mid];
        if(total_time <= t) return true;
    }
    return false;
}

int main()
{
    cin>>n>>t;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    //对能完成的题目数量进行二分
    int l = -1 , r = n + 1;
    while(l + 1 != r)
    {
        int mid = (l + r)>>1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout<<l<<endl;

    return 0;
}