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

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

with open("img1_1786621659.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
eligible = [c for c in totals if totals[c] <= 150000]
first = max(eligible, 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)

Для первого числа отобраны клиент 1006: 148122 Кбайт. Среди подходящих устройств получен требуемый результат 1006.
Для второго числа выбраны копии 18:37:09: 23285 Кбайт; 18:09:36: 23281 Кбайт. Получаем 46566 Кбайт.
Проверка: найдено 1112 резервных копий, из них 548 до полудня и 564 начиная с полудня. В конце осталось 5477 Кбайт. Сумма объёмов всех копий и этого остатка равна сумме всех запросов 24941975 Кбайт.
Независимый расчёт использовал префиксные суммы запросов. Для каждого начала блока бинарным поиском найдена последняя граница, при которой сумма не превышает K; следующий запрос вызывает копию. Все границы блоков и объёмы совпали с пошаговой симуляцией.
Сортировка и выбор требуемых максимумов занимают O(N log N) времени; симуляция — O(N). Память для журнала, сумм и списка копий O(N).
Ответ: 1006 46566.