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

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

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

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

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

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

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

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$ соответственно. Ответ для приведённого примера: $404$ $242000$.

from collections import defaultdict

f = open('26-26.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 >= '12:00:00':              # копия сделана не ранее 12:00:00
            backups.append(cur)
        cur = 0
    cur += s
    total[int(c)] += s

best = max((v for v in total.values() if v <= 150000))
client = min(c for c, v in total.items() if v == best)

backups.sort(reverse=True)

print(client, backups[0] + backups[1])   # 1006 46566