STASYAMBA BOG NO WA 4

#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:66777216")
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <ctime>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <deque>
#include <cassert>
#include <cstdlib>
#include <bitset>
#include <algorithm>
#include <string>
#include <list>
#include <fstream>
#include <cstring>
#include <climits>
#include <random>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef multiset<ll> mll;

#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define for1(i, n) for (int i = 1; i <= (int)n; i++)
#define forq(i, s, t) for (int i = s; i <= t; i++)
#define ford(i, s, t) for (int i = s; i >= t; i--)
#define mk make_pair
#define inb push_back
#define outb pop_back
#define ump unordered_map
#define all(v) v.begin(), v.end()
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define randint(x,y)
#define randlong(x, y)
#define TASK ""

const double eps = 1e-15;
const double pi = acos(-1.0);

const int MAXN = (int)1e5 + 7;
const int INF = (ll)2e9;
const ll LINF = (ll)8e18;
const int MOD = (ll)1e9 + 7;

void gen();
int solve();

int main()
{
#ifdef _DEBUG
    gen();
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("test.txt", "w", stderr);
    double tstart = TIME;
#else
    //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
    //freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout), freopen("test.txt", "w", stderr);
#endif
    solve();
#ifdef _DEBUG
    double tend = TIME;
    cerr << tend - tstart << " s.\n";
#endif
    return 0;
}

void gen()
{
    freopen("input.txt", "a+", stdout);
    srand(time(0));
    return;
}

int n, m;
vll a;

bool check(int x)
{
    vll dp(n + 2);
    mll p;
    p.insert(0);
    for (int i = 1, l = 0; i <= n + 1; i++)
    {
        if (i - l > x)
            p.erase(p.find(dp[l++]));
        p.insert(dp[i] = a[i - 1] + *p.begin());
    }
    return dp[n + 1] <= m;
}

int solve()
{
    cin >> n >> m;
    a.resize(n + 1);
    forn(i, n)
    {
        scanf("%I64d",&a[i]);
    }
    int l = 0, r = n + 1;
    for1 (i, 100)
    {
        int s = (l + r) / 2;
        if (check(s))
            r = s;
        else
            l = s;
    }
    printf("%d", r);
    return 0;
}