1. Идея

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

Если для каждого такого отрезка считать сумму заново, получится слишком медленно: на один отрезок уходит O(k), а всего отрезков около n, значит общее время будет O(nk). При n до 2 * 10^5 это может быть слишком много.

Поэтому используем префиксные суммы. Они позволяют быстро находить сумму любого подотрезка за O(1) после предварительной обработки.

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

Построим массив префиксных сумм pre, где:

• pre[0] = 0
• pre[i] — сумма первых i элементов массива

Тогда сумма элементов на отрезке от l до r включительно равна:

pre[r + 1] - pre[l]

В нашей задаче нужны только отрезки длины k.

Если отрезок начинается в позиции i, то его сумма равна:

pre[i + k] - pre[i]

Начальные позиции таких отрезков: от 0 до n - k.

Значит, достаточно перебрать все i в этом диапазоне и взять максимум.

3. Алгоритм

1. Считать n и k.
2. Считать массив a из n чисел.
3. Построить массив префиксных сумм pre длины n + 1.
4. Инициализировать ответ суммой первого окна длины k:
   • ans = pre[k] - pre[0]
5. Перебрать все остальные начала окон:
   • для каждого i от 1 до n - k
   • вычислить cur = pre[i + k] - pre[i]
   • обновить ans, если cur > ans
6. Вывести ans.

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

Префиксные суммы хранят накопленные суммы массива.

Если pre[i] — сумма первых i элементов, то:

• pre[i + k] — сумма первых i + k элементов
• pre[i] — сумма первых i элементов

Если из суммы первых i + k элементов вычесть сумму первых i, останется сумма элементов с индекса i до i + k - 1, то есть ровно сумма окна длины k, начинающегося в i.

Мы перебираем все возможные начала таких окон, а значит рассматриваем все отрезки длины k без пропусков.

Среди их сумм выбирается максимум, поэтому полученный ответ и есть максимальная суммарная нагрузка среди всех интервалов из k подряд идущих минут.

5. Сложность

• Построение префиксных сумм: O(n)
• Перебор всех окон: O(n)
• Общая сложность: O(n)
• Дополнительная память: O(n)

Важно использовать 64-битный целочисленный тип, потому что сумма может быть большой. В C++ это long long.

6. Код на C++17

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

int main() {
    int n, k;
    cin >> n >> k;

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

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

    long long ans = pre[k] - pre[0];
    for (int i = 1; i <= n - k; i++) {
        long long cur = pre[i + k] - pre[i];
        if (cur > ans) {
            ans = cur;
        }
    }

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

7. Код на Python 3

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

pre = [0] * (n + 1)
for i in range(n):
    pre[i + 1] = pre[i] + a[i]

ans = pre[k] - pre[0]
for i in range(1, n - k + 1):
    cur = pre[i + k] - pre[i]
    if cur > ans:
        ans = cur

print(ans)