Задание EGEINF0AF4A5: Сортировка, отбор и моделирование

Решение.
В исходном журнале N = 15001 запросов, вместимость раздела K = 26107 Кбайт. Упорядочим запросы по времени. Строки времени имеют одинаковый формат ЧЧ:ММ:СС, поэтому их обычная сортировка совпадает с хронологической.
Объёмы по клиентам и резервные копии считаем отдельно. Для каждого клиента складываем объёмы его запросов. Для раздела храним used — сумму данных, записанных после последнего освобождения.
Перед очередным запросом объёма size проверяем used + size > K. Если места не хватает, создаётся копия объёма used во время текущего запроса, затем раздел освобождается. Только после этого записывается новый запрос. Поэтому он не входит в создаваемую перед ним копию.
При used + size = K запрос помещается полностью и копия ещё не создаётся. В конце журнала оставшиеся данные сами по себе не образуют резервную копию: по условию копирование вызывается нехваткой места для следующего запроса.
До обработки первого запроса used = 0. После каждого шага used равен сумме именно тех запросов, которые находятся в разделе сейчас. Описанная проверка сохраняет этот инвариант и перечисляет все моменты копирования. Для ограничения по времени используем момент создания копии, а не время первого записанного в неё запроса.
Для первого числа выбираем идентификатор клиента с наибольшей суммой данных за весь день. Для второго числа оставляем копии с временем строго меньше 12:00:00 и складываем два наибольших объёма. Ограничение до полудня относится только к резервным копиям.
Сохраните скачанный файл рядом с программой под исходным именем. Программа на Python:

with open("img1_1786620629.txt") as f:
    n, capacity = map(int, f.readline().split())
    log = []
    for line in f:
        time, client, size = line.split()
        log.append((time, int(client), int(size)))
log.sort(key=lambda row: row[0])
totals = {}
morning = {}
backups = []
used = 0
for time, client, size in log:
    totals[client] = totals.get(client, 0) + size
    if time < '12:00:00':
        morning[client] = morning.get(client, 0) + size
    if used + size > capacity:
        backups.append((time, used))
        used = 0
    used += size
first = max(totals, key=totals.get)
sizes = sorted((size for time, size in backups if time < '12:00:00'), reverse=True)
second = sizes[0] + sizes[1]
print(first, second)

Для первого числа отобраны клиент 7040: 303454 Кбайт. Среди подходящих устройств получен требуемый результат 7040.
Для второго числа выбраны копии 02:26:41: 26102 Кбайт; 08:37:22: 26102 Кбайт. Получаем 52204 Кбайт.
Проверка: найдено 1072 резервных копий, из них 534 до полудня и 538 начиная с полудня. В конце осталось 23807 Кбайт. Сумма объёмов всех копий и этого остатка равна сумме всех запросов 26981045 Кбайт.
Независимый расчёт использовал префиксные суммы запросов. Для каждого начала блока бинарным поиском найдена последняя граница, при которой сумма не превышает K; следующий запрос вызывает копию. Все границы блоков и объёмы совпали с пошаговой симуляцией.
Сортировка и выбор требуемых максимумов занимают O(N log N) времени; симуляция — O(N). Память для журнала, сумм и списка копий O(N).
Ответ: 7040 52204.