26. Прикладная задача: #298100

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные – в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу обработки журнала работы сервера и определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, созданных не позднее $11{:}59{:}59$.

Входные данные

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N < 1000000$) – количество строк в журнале и $K$ ($K < 1000000$) – вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: $C$ ($C < 1000000$) – идентификатор клиентского устройства и $S$ ($S < K$) – объём данных запроса в Кбайт.

Выходные данные

В ответе запишите два числа: сначала идентификатор устройства, с которого был передан наибольший суммарный объём данных, а затем сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, выполненных не позднее $11{:}59{:}59$.

Типовой пример организации данных во входном файле:

8 140000
01:01:01 101 20000
03:03:03 202 110000
05:05:05 101 90000
07:07:07 303 62000
10:10:10 101 48000
15:15:15 202 12000
21:21:21 303 120000
23:23:23 404 134000

При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в $05{:}05{:}05$ (в объёме $130000$ Кбайт), в $07{:}07{:}07$ (в объёме $90000$ Кбайт), в $21{:}21{:}21$ (в объёме $122000$ Кбайт) и в $23{:}23{:}23$ (в объёме $120000$ Кбайт). Всего на сервер передано $596000$ Кбайт данных: $158000$, $122000$, $182000$ и $134000$ Кбайт от клиентов с идентификаторами $101$, $202$, $303$ и $404$ соответственно. Ответ для приведённого примера: $303$ $220000$.

from collections import defaultdict

f = open('26-30.txt')
n, K = map(int, f.readline().split())

total = defaultdict(int)
backups = []
cur = 0

for _ in range(n):
    t, c, s = f.readline().split()
    s = int(s)
    if cur + s > K:                  # свободной памяти не хватает
        if t <= '11:59:59':          # копия создана не позднее 11:59:59
            backups.append(cur)
        cur = 0
    cur += s
    total[int(c)] += s

best = max(total, key=lambda c: total[c])
backups.sort(reverse=True)

print(best, backups[0] + backups[1])   # 7040 52204