Задание EGEINFE8867C: Эффективная обработка данных и кластеры

Решение.

Обрабатываем два приложенных текстовых файла отдельно. В файле A содержится 775 записей, в файле B — 991698. Заголовок задаёт параметры и не является элементом последовательности. Порядок исходных записей сохраняем. Числа из иллюстративного примера не заменяют данные файлов.

В первой строке файла записано K, во второй — N. Расстояние между позициями равно разности их номеров. Для i < j < k нужны j − i ≥ K и k − j ≥ K. Тогда k − i ≥ 2K выполняется автоматически, но одной проверки крайнего расстояния недостаточно.

Фиксируем позицию j. Среди допустимых элементов слева поддерживаем максимум на позициях до j − K включительно: перед проверкой j добавляем элемент aⱼ₋ₖ. Справа нужен максимум на позициях от j + K до конца; заранее строим массив таких экстремумов обратным проходом. При фиксированном aⱼ сумма монотонно возрастает по остальным слагаемым. Независимый выбор нужного экстремума с каждой стороны даёт максимум для данного j.

Перебираем j от K до N − K − 1 в нумерации программы от нуля. Все допустимые варианты представлены, а границы исключают повторное использование позиции. Начальное значение best = None не ограничивает возможный знак суммы. Целые числа Python точно хранят и большие произведения.

Распакуем архив и положим указанные в программе текстовые файлы рядом с ней. Программа печатает результат для A, затем для B:

from array import array

def solve(name):
    with open(name, encoding="utf-8-sig") as f:
        k = int(f.readline())
        n = int(f.readline())
        a = array("q", (int(f.readline()) for _ in range(n)))

    right = array("q", a)
    for i in range(n - 2, -1, -1):
        right[i] = max(right[i], right[i + 1])

    left = a[0]
    best = None
    for j in range(k, n - k):
        left = max(left, a[j - k])
        value = left + a[j] + right[j + k]
        if best is None or value > best:
            best = value
    return best

print(solve('313_27_A.txt'), solve('313_27_B.txt'))

Время O(N), память O(N). Считывание и все арифметические действия выполняются над целыми числами; округление вычисленных ответов не требуется.

Проверка на исходных файлах. Номера элементов ниже отсчитываются от 1; полный алгоритм проверяет все допустимые варианты, а указанные позиции показывают достижение найденного результата.

Файл A: (55465) + (77283) + (55170) = 187918. Разности соседних выбранных номеров равны 157, 167; каждая не меньше K = 155.

Файл B: (3678) + (5575) + (7974) = 17227. Разности соседних выбранных номеров равны 323306, 187443; каждая не меньше K = 165283.

Ответ: 187918 17227.