Курьер
ограничение времени 1 секунда
ограничение памяти 256mb
ввод стандартный ввод или input.txt
вывод стандартный вывод или output.txt
курьеру васе поручили доставить n посылок. вася начинает работать в первый день и каждый день может доставить ровно одну посылку. про каждую посылку известен последний день, когда ее можно доставить di, и штраф wi, который придется заплатить, если посылка не будет доставлена в срок.

васе решить, в каком порядке доставлять посылки, чтобы суммарный штраф был как можно меньше.

например, если есть 3 посылки, первую необходимо доставить в первый день и штраф за опоздание 2, вторую также необходимо доставку в первый день и штраф за опоздание 3, а третью необходимо доставить не позже третьего дня и штраф за опоздание 1, то оптимально доставить сначала вторую, потом третью, а затем первую посылку. в этом случае не в срок доставлена только первая посылка и штраф составляет 2. доставить одновременно первую и вторую посылку в срок невозможно.

формат ввода
в первой строке дано единственное натуральное число n (1 ≤ n ≤ 200 000) — количество посылок.

затем следует n строк, в каждой из которых содержится по два числа di и wi (1 ≤ di ≤ 200 000, 1 ≤ wi ≤ 200 000) — последний день, когда можно доставить посылку без штрафа и стоимость опоздания для i-й посылки.

формат вывода
в первой строке выведите единственное число, равное минимально возможному суммарному штрафу. во второй строке через пробел выведите n чисел, где i-е число — день, в который необходимо доставить i-ю посылку.

если возможно несколько оптимальных расписаний, выведите любое из них.

240

407

Посмотреть ответы 2

Ответы на вопрос:

timurev

Информатика

4,5(49 оценок)

ответ: надо доставит 6 посылок

объяснение:

KasiaW

Информатика

4,5(8 оценок)

каскадная модель -RAD- модель

Задай свой вопрос

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.