printРабочее место участника

printЗадачи

921. Заседания

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Перед праздниками Шеф получает очень много приглашений на торжественные заседания. Чтобы лучше планировать свое время, Шеф ввёл правило, чтобы в каждом `i`-ом приглашении был чётко указан отрезок времени заседания `[a_i;\ b_i]`. Кроме того, Шеф устанавливает каждому заседанию "важность" `c_i`. Шеф не любит половинчатых решений, поэтому или находится на заседании всё указанное время, или не приходит на него вовсе. Между посещениями заседаний должен быть хотя бы минимальный перерыв, т.е. Шеф может успеть на `j`-е (по списку приглашений) после `i`-го, если и только если `a_j` > `b_i`. Напишите программу, помогающую Шефу посетить заседания с как можно большей суммарной важностью. Если возможны разные наборы с одинаковой максимальной суммарной важностью, выбрать тот, где меньше суммарная длина заседаний.
Ввод содержит сначала количество заседаний `N`, где `2\ ≤\ N\ ≤\ 30\ 000`, затем `N` троек (`a_i`, `b_i`, `c_i`). Гарантированно, что `0\ ≤\ a_i\ <\ b_i\ <\ 10^9`, все `c_i` натуральные и их сумма не превышает `10^9`.
Программа должна вывести через пробел суммарную важность и суммарную длительность выбранных заседаний.

Пример ввода 1

3 1 5 3 4 9 4 6 11 2

Вывод для примера 1

5 9

Пример ввода 2

3 1 5 3 5 9 5 6 11 2

Вывод для примера 2

5 4
Источник: Всеукраинская Интернет-олимпиада по информатике NetOI-2006
loading