Обработка журнала сервера
Сервер выполняет запросы на передачу данных. Для каждого запроса в журнале указаны время регистрации, идентификатор клиента и объём переданных данных. Переданные данные сохраняются в специальном разделе памяти сервера вместимостью $K$ Кбайт. Каждый раз, когда для очередного запроса недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных данных, после чего освобождает раздел и продолжает выполнение запросов. Определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов двух наибольших резервных копий, созданных не позднее 11:59:59.
В первой строке входного файла находятся натуральные числа $N$ и $K$: количество записей журнала и вместимость раздела памяти в Кбайт. В каждой из следующих $N$ строк записаны время в формате ЧЧ:ММ:СС, идентификатор клиента $C$ и объём данных $S$ в Кбайт. Выведите два числа: сначала идентификатор клиента, затем сумму объёмов двух наибольших подходящих резервных копий.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Какие данные нужно накапливать отдельно для каждого клиента, а какие — для каждой резервной копии?
2Наводящая — какие числа считатьуровень 2 из 3
Храните суммы объёмов по идентификаторам клиентов и текущий объём данных в разделе. Перед добавлением запроса, который не помещается, сохраните текущий объём как резервную копию.
3Прямая — фактически решениеуровень 3 из 3
При обработке каждой записи: если текущий объём плюс $S$ больше $K$, добавьте текущий объём в список копий и обнулите его; затем прибавьте $S$. После прохода найдите максимальную сумму по клиентам и сумму двух максимальных копий со временем не позднее 11:59:59.