Серия обедов по бюджету

В школьной столовой на стене висит табличка: сколько рублей стоит обед в каждый из ближайших n дней. Ты хочешь выбрать подряд идущие дни, когда будешь обедать, так чтобы суммарно потратить не больше k рублей.

Найди максимальное количество подряд идущих дней, которое можно выбрать.

Важно: числа могут быть большими (как на олимпиадах), ориентируйся на 64-битные значения.

Формат ввода

В первой строке даны два целых числа n и k — количество дней и бюджет. Во второй строке даны n целых чисел a1, a2, ..., an — стоимость обеда в каждый день.

Формат вывода

Выведи одно целое число — максимальную длину отрезка подряд идущих дней, сумма стоимостей на котором не превосходит k.

Ограничения

• 2 ≤ n ≤ 35000
• 0 ≤ k ≤ 10^12
• 0 ≤ ai ≤ 10^6
• Все ai неотрицательные.

Пример

Ввод:

7 10
2 3 5 1 1 1 7

Вывод:

4

(Можно взять дни со стоимостями 3, 5, 1, 1: сумма 10, длина 4.)

Ключевое наблюдение: все цены ai неотрицательные. Значит, если мы расширяем отрезок вправо, сумма только растёт, а если сдвигаем левую границу вправо — сумма только уменьшается. Это позволяет искать ответ за один проход, не перебирая все отрезки.

Приём: два указателя / скользящее окно. Поддерживаем отрезок [l..r] и его сумму s. Всегда стараемся держать условие s <= k. Если сумма стала слишком большой, «ужимаем» окно слева, пока снова не уложимся в бюджет.

План:

• Инициализируй l = 0, s = 0, best = 0.
• Для каждого r от 0 до n-1:
• добавь новый день: s += a[r].
• пока s > k, сдвигай левую границу: s -= a[l], l += 1.
• теперь отрезок [l..r] допустим, обнови ответ: best = max(best, r - l + 1).
• Выведи best.

Сложность: O(n) по времени, потому что каждый указатель двигается только вперёд, и O(1) по памяти.

Частая ошибка: пытаться применять этот метод, когда в массиве могут быть отрицательные числа — тогда монотонность суммы ломается и окно не работает. Здесь всё ок, потому что ai >= 0. Также не забудь про 64-битную сумму (в Python это автоматически).