Ctrl K

Сумма на длину меньше лимита

Сложная
Дан массив положительных чисел loads и число limit. Весом отрезка массива (непрерывного куска) назовём сумму его элементов, умноженную на его длину. Например, вес [2, 5, 1] равен (2 + 5 + 1) · 3 = 24. Посчитайте, сколько непустых отрезков имеют вес **строго меньше** limit.
Пример 1
loads=[3, 1, 2, 6], limit=8 → 5

Подходят [3], [1], [2], [6] и [1, 2] с весом (1 + 2) · 2 = 6. У [3, 1] вес 8 — это не меньше лимита.

Пример 2
loads=[2, 2], limit=3 → 2

Обе одиночные двойки весят 2. Пара весит (2 + 2) · 2 = 8.

Пример 3
loads=[5, 4, 1], limit=100 → 6
Ограничения
  • 1 ≤ len(loads) ≤ 10⁵
  • 1 ≤ loads[i] ≤ 10⁵
  • 1 ≤ limit ≤ 10¹⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКороткий отрезок с нужной суммой СложнаяЯгоды вдоль тропинки СложнаяСамая длинная серия станков в бюджет СложнаяСвязь в самом глухом селе СложнаяБольше одинаковых за бюджет Сложная
загружаем Python…
Вход
loads=[3, 1, 2, 6], limit=8
Ожидается
5

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 81 тест на сервере, включая скрытые.