1. Идея

Нужно посчитать количество подотрезков массива, у которых сумма не превосходит S.

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

Будем поддерживать окно [l..r]:

• правую границу r двигаем слева направо;
• сумму элементов внутри окна храним в переменной cur;
• если сумма стала больше S, двигаем левую границу l, пока сумма снова не станет допустимой.

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

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

Наблюдение 1

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

Это важно: если сумма стала слишком большой, уменьшить её можно только сдвигом левой границы вправо.

Наблюдение 2

Для фиксированного r, если отрезок [l..r] уже имеет сумму не больше S, то любой отрезок [x..r], где x >= l, тоже будет иметь сумму не больше S.

Почему? Потому что мы просто убираем несколько неотрицательных элементов слева, а сумма от этого не увеличивается.

Значит, если найден минимальный допустимый l, то подходят все начала:

• l,
• l + 1,
• ...
• r.

Их ровно r - l + 1.

Наблюдение 3

Левая и правая границы двигаются только вправо. Поэтому общий алгоритм работает за линейное время.

3. Алгоритм

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

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

Докажем корректность.

Рассмотрим некоторый момент, когда правая граница равна r.

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

После окончания цикла while выполняются два факта:

1. Сумма отрезка [l..r] не больше S.
2. Если взять любой индекс меньше l, то отрезок [x..r] уже не подходит.

Почему второе верно? Потому что l сдвигался вправо именно до тех пор, пока сумма не стала допустимой. Значит, все более левые начала давали слишком большую сумму.

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

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

Значит, количество всех подходящих подотрезков, заканчивающихся в r, равно ровно r - l + 1.

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

5. Сложность

Каждый элемент:

• один раз добавляется в сумму при движении r,
• не более одного раза удаляется из суммы при движении l.

Поэтому:

• время: O(n),
• память: O(n) на хранение массива.

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 cur = 0;
    long long ans = 0;
    int l = 0;

    for (int r = 0; r < n; r++) {
        cur += a[r];
        while (l <= r && cur > S) {
            cur -= a[l];
            l++;
        }
        ans += (long long)(r - l + 1);
    }

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

7. Код на Python 3

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

l = 0
cur = 0
ans = 0

for r in range(n):
    cur += a[r]
    while l <= r and cur > S:
        cur -= a[l]
        l += 1
    ans += r - l + 1

print(ans)