1. Идея

Нужно найти самый длинный непрерывный отрезок массива, сумма элементов на котором не больше S.

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

Будем поддерживать текущий отрезок [l, r] и его сумму.

• Двигаем правую границу r слева направо.
• Добавляем a[r] в сумму.
• Если сумма стала больше S, двигаем левую границу l вправо, пока сумма снова не станет допустимой.
• После этого отрезок [l, r] — самый длинный допустимый отрезок, оканчивающийся в r, и можно обновить ответ.

2. Наблюдения

Наблюдение 1

Все элементы массива положительные: a_i >= 1.

Это очень важно. Если мы расширяем отрезок вправо, сумма только увеличивается. Если сдвигаем левую границу вправо, сумма только уменьшается.

Поэтому можно жадно поддерживать окно:

• если сумма слишком большая, нужно уменьшать её только сдвигом l;
• после этого нет смысла двигать l назад.

Наблюдение 2

Для каждого фиксированного r после всех сдвигов l мы получаем минимальную возможную левую границу, при которой сумма на [l, r] уже не превышает S.

Значит, длина r - l + 1 — максимальная длина допустимого отрезка, который заканчивается в позиции r.

Наблюдение 3

Каждый указатель движется только вправо:

• r проходит массив один раз;
• l тоже проходит массив не более одного раза.

Отсюда получается линейная сложность.

3. Алгоритм

1. Считываем n, S и массив a.
2. Инициализируем:
   • l = 0 — левая граница окна,
   • sum = 0 — сумма на текущем окне,
   • ans = 0 — лучший ответ.
3. Для каждого r от 0 до n - 1:
   • прибавляем a[r] к sum;
   • пока sum > S, вычитаем a[l] из sum и увеличиваем l;
   • теперь сумма на окне не больше S, значит можно обновить ответ длиной r - l + 1.
4. Выводим ans.

4. Почему это работает

Докажем, что алгоритм действительно находит максимальную длину.

Когда правая граница равна r, мы рассматриваем некоторый текущий отрезок [l, r].

После добавления a[r] сумма могла стать больше S. Тогда мы двигаем l вправо, пока сумма снова не станет не больше S.

Так как все элементы положительные, при увеличении l сумма строго уменьшается или, по крайней мере, не увеличивается. Значит, процесс обязательно корректно находит первую позицию l, с которой сумма на [l, r] уже допустима.

Теперь важно понять, почему длина этого окна максимальна среди всех допустимых отрезков, заканчивающихся в r.

• Если взять любую позицию левее l, то сумма станет больше, потому что мы добавим к уже допустимому окну ещё положительные числа.
• Значит, никакой отрезок [l', r] с l' < l не подходит.
• Следовательно, [l, r] — самый длинный допустимый отрезок, оканчивающийся в r.

Мы проверяем это для каждого r, поэтому среди всех таких отрезков найдём глобально максимальную длину.

Значит, алгоритм корректен.

5. Сложность

• Правая граница r двигается от 0 до n - 1, то есть n шагов.
• Левая граница l тоже двигается только вправо и суммарно не более n раз.

Итоговая сложность:

• по времени: O(n)
• по памяти: O(1), если не считать сам входной массив

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long S;
    cin >> n >> S;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long sum = 0;
    int l = 0;
    int ans = 0;

    for (int r = 0; r < n; r++) {
        sum += a[r];

        while (l <= r && sum > S) {
            sum -= a[l];
            l++;
        }

        if (sum <= S) {
            int len = r - l + 1;
            if (len > ans) ans = len;
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n, S = map(int, input().split())
a = list(map(int, input().split()))

l = 0
current_sum = 0
answer = 0

for r in range(n):
    current_sum += a[r]

    while l <= r and current_sum > S:
        current_sum -= a[l]
        l += 1

    if current_sum <= S:
        length = r - l + 1
        if length > answer:
            answer = length

print(answer)