1. Идея

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

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

Здесь подходит метод скользящего окна:

• сначала считаем сумму первого отрезка длины k;
• затем двигаем окно на один вправо:
  • прибавляем новый элемент справа;
  • вычитаем элемент, который ушёл слева.

Так мы получаем сумму каждого следующего окна за O(1).

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

1. Любой допустимый ответ — это подотрезок ровно длины k.

2. Если известна сумма отрезка a[l] ... a[r], где r - l + 1 = k, то сумма следующего отрезка длины k, то есть a[l+1] ... a[r+1], вычисляется так:

   • берём старую сумму;
   • вычитаем a[l];
   • прибавляем a[r+1].

3. Так как числа могут быть большими по модулю, сумма может не поместиться в 32-битный тип. Поэтому:

   • в C++ нужен long long;
   • в Python всё и так работает, потому что int поддерживает большие значения.

4. В условии просят вывести наименьший l, если максимум встречается несколько раз. Значит:

   • обновлять ответ нужно только если нашли строго большую сумму;
   • если сумма равна текущему максимуму, ничего менять не надо, потому что более ранний отрезок уже был найден раньше.

3. Алгоритм

1. Считать n, k и массив a.
2. Посчитать сумму первых k элементов — это сумма первого окна.
3. Запомнить:
   • current_sum — сумма текущего окна,
   • best_sum — лучшая найденная сумма,
   • best_l = 1 — начало лучшего окна в 1-based нумерации.
4. Для каждого r от k до n - 1:
   • добавить a[r],
   • вычесть a[r - k],
   • получить начало текущего окна:
     • l = r - k + 2 в 1-based нумерации;
   • если current_sum > best_sum, обновить best_sum и best_l.
5. Вывести best_sum и best_l.

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

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

Рассмотрим все подотрезки длины k по порядку слева направо.

Шаг 1. Корректность вычисления сумм окон

Сначала алгоритм считает сумму первого окна: a[1] + a[2] + ... + a[k].

Дальше при переходе к следующему окну длины k:

• левый элемент старого окна удаляется,
• справа добавляется новый элемент.

Значит, если текущее окно было a[l] ... a[l+k-1], то следующее окно — это a[l+1] ... a[l+k], и его сумма равна:

• старая сумма,
• минус a[l],
• плюс a[l+k].

Следовательно, на каждом шаге current_sum действительно равна сумме текущего окна длины k.

Шаг 2. Перебираются все возможные окна

Первое окно начинается в позиции 1, последнее — в позиции n - k + 1.

Цикл последовательно сдвигает окно на один вправо, поэтому будут рассмотрены все возможные подотрезки длины k и ни один не пропустится.

Шаг 3. Правильный выбор лучшего ответа

Во время перебора поддерживается лучшая найденная сумма best_sum и соответствующее начало best_l.

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

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

Значит, после обработки всех окон:

• best_sum — максимальная сумма среди всех подотрезков длины k,
• best_l — минимальный индекс начала среди всех оптимальных подотрезков.

Следовательно, алгоритм корректен.

5. Сложность

• Сумма первого окна считается за O(k).
• Затем каждое из оставшихся окон обрабатывается за O(1).
• Всего получается O(n) по времени.

По памяти:

• хранится массив из n чисел,
• значит, используется O(n) памяти.

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];
    }

    long long current_sum = 0;
    for (int i = 0; i < k; i++) {
        current_sum += a[i];
    }

    long long best_sum = current_sum;
    int best_l = 1;

    for (int r = k; r < n; r++) {
        current_sum += a[r];
        current_sum -= a[r - k];
        int l = r - k + 2; // 1-based index of current window start

        if (current_sum > best_sum) {
            best_sum = current_sum;
            best_l = l;
        }
    }

    cout << best_sum << ' ' << best_l << '\n';
    return 0;
}

7. Код на Python 3

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

current_sum = sum(a[:k])
best_sum = current_sum
best_l = 1

for r in range(k, n):
    current_sum += a[r]
    current_sum -= a[r - k]
    l = r - k + 2  # 1-based index of current window start
    if current_sum > best_sum:
        best_sum = current_sum
        best_l = l

print(best_sum, best_l)