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

Решение.

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

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

Фиксируем позицию j. Среди допустимых элементов слева поддерживаем максимум на позициях до j − K включительно: перед проверкой j добавляем элемент aⱼ₋ₖ. Справа нужен максимум на позициях от j + K до конца; заранее строим массив таких экстремумов обратным проходом. Все множители положительны, поэтому произведение монотонно по каждому выбранному множителю. Независимый выбор нужного экстремума с каждой стороны даёт максимум для данного 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('319_27_A.txt'), solve('319_27_B.txt'))

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

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

Файл A: 5569 · 5598 · 5585 = 174113838270. Разности соседних выбранных номеров равны 164, 156; каждая не меньше K = 153.

Файл B: 5064 · 5055 · 5048 = 129221328960. Разности соседних выбранных номеров равны 166243, 166237; каждая не меньше K = 166233.

Ответ: 174113838270 129221328960.