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

Решение.

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

Вместимость контейнера c = 12. Для пункта с t пробирками нужно w = ⌈tc⌉ контейнеров. В программе divmod даёт целую часть и остаток; прибавляем один, если остаток положителен. Округляем каждый пункт отдельно: объединять остатки из разных пунктов нельзя. Позиции x уже упорядочены по дороге.

Заголовок содержит N и M. Для лаборатории в существующем пункте x допустимы ровно позиции от x − M до x + M включительно. Суммируем их w; контейнеры самого пункта тоже входят, как показано в примере условия. Ищем максимум этой суммы, а не максимум числа пробирок и не минимум транспортной стоимости.

Два указателя ограничивают подходящий отрезок упорядоченных пунктов. Для очередного центра добавляем справа все xᵢ ≤ x + M, затем убираем слева все xᵢ < x − M. Текущее inside равно точной сумме весов оставшегося отрезка. При движении центра вправо обе границы могут только двигаться вправо. Каждый пункт добавляется и удаляется не более одного раза; проверяются все разрешённые места лаборатории.

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

from array import array

def solve(name):
    capacity = 12
    x = array("q")
    w = array("q")
    with open(name, encoding="utf-8-sig") as f:
        n, distance = map(int, f.readline().split())
        for _ in range(n):
            position, tubes = map(int, f.readline().split())
            quotient, remainder = divmod(tubes, capacity)
            x.append(position)
            w.append(quotient + (remainder > 0))

    left = right = 0
    inside = best = 0
    for center in x:
        while right < n and x[right] <= center + distance:
            inside += w[right]
            right += 1
        while left < right and x[left] < center - distance:
            inside -= w[left]
            left += 1
        best = max(best, inside)
    return best

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

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

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

Обе крайние позиции находятся не дальше M от лаборатории. Сумма контейнеров по всем строкам между ними совпала с результатом; независимый поиск границ двоичным поиском проверил каждый возможный центр.

Ответ: 332 27697.