Войти
или
Зарегистрироваться
Маркетплейс
Курсы
Учебник
Учебник 2.0
ЕГЭ
ОГЭ
Олимпиады
Рубрикатор
Компилятор
Онлайн Компилятор
Компилятор Python с отладкой
Питон - Черепашка
Эмулятор исполнителя Робот - Кумир
Редактор HTML Code
SQLite Studio - работа с БД
Клавиатурный тренажёр программиста
Олимпиадный тренинг
Задача
.
Аэропорт_2
Задача
Темы:
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения, состоящей из множества ячеек. Для каждой ячейки известна стоимость хранения одного багажа.
В заявке указаны время сдачи багажа (в минутах от начала суток) и время хранения багажа в ячейке. Багаж каждого пассажира занимает ровно одну ячейку и может поместиться в любой ячейке. Если в момент сдачи багажа свободных ячеек нет, пассажир уходит. Если свободных ячеек несколько, пассажир выбирает свободную ячейку с наименьшей стоимостью, а среди ячеек с одинаковой стоимостью — ячейку с наименьшим номером. Размещение багажа в ячейке или её освобождение происходит моментально, после освобождения следующий пассажир может сразу же занять эту ячейку.
Определите сумму, которая потребуется для хранения багажа тех пассажиров, которые смогут оставить свой багаж в течение 15 ч (от начала суток), а также номер ячейки, в которой будет размещён последний сданный багаж за 15 ч.
Входные
данные
В первой строке входного файла находятся два числа:
N
количество ячеек (натуральное число, не превышающее 10 000) и число
К
количество пассажиров (натуральное число, не превышающее 10 000). Каждая из следующих
N
строк содержит одно натуральное число, не превышающее 1000: стоимость хранения багажа в ячейке. Стоимость хранения указана в порядке нумерации ячеек, начиная с первой.
Каждая из последующих
К
строк содержит два натуральных числа, не превышающих 1440: указанное в заявке время размещения багажа в ячейке (в минутах от начала суток) и срок хранения багажа (в минутах). Гарантируется, что время размещения багажа любых двух пассажиров различно.
Запишите в ответе два целых числа: сначала общую стоимость хранения сданных за 15 ч багажей, затем номер ячейки последнего сданного багажа за 15 ч.
Типовой пример организации данных во входном
файле
2 5
70
60
30
30
40
960
59
1
61
939
1010
430
Пример организации данных приведён для двух ячеек и пяти пассажиров.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
1000
ms
256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач
Статистика успешных решений по компиляторам