Перед святами Шеф отримує дуже багато запрошень на святкові
засідання. Щоб краще планувати свій час, Шеф увів правило, щоб у кожному
запрошенні був чітко
вказаний відрізок часу [ai; bi],
коли триває засідання. Крім того, Шеф встановлює кожному засіданню “важливість”
ci. Шеф не любить половинчатих рішень, тому або перебуває на
засіданні увесь вказаний час, або не приходить на
нього зовсім. Між відвідинами засідань має бути хоча б мінімальна перерва, тобто Шеф може встигнути на
j-те (за списком запрошень)
після i-го, тоді й
тільки тоді, коли aj>bi.Напишіть програму, що допомагатиме Шефу відвідати
засідання з якомога більшою сумою важливості. Якщо можливі різні набори
засідань з
однаковою максимальною сумарною важливістю, вибрати той, де менша сумарна тривалість
засідань.
Технічні умови Програма читає з клавіатури спочатку кількість заходівN, де 2<= N <= 5 000, потім N трійок
(ai, bi, ci).
Гарантовано, що 0 <= ai < bi< 109, усі ci натуральні та їхня сума не перевищує
109. Програма має вивести на екран через пропуск суму
важливості та суму тривалості вибраних засідань.
Приклади.
Вхід
Вихід
3 1 5 3 4 9 4 6 11 2
5 9
3 1 5 3 5 9 5 6 11 2
5 4
Задача Chief2
Перед праздниками Шеф получает очень много приглашений на
торжественные заседания. Чтобы лучше планировать свое время, Шеф ввёл правило,
чтобы в каждом i-ом приглашении был чётко указан отрезок времени заседания
[ai; bi].
Кроме того, Шеф устанавливает каждому заседанию “важность”
ci. Шеф не любит
половинчатых решений, поэтому или находится на заседании всё указанное время,
или не приходит на него вовсе. Между посещениями заседаний должен быть хотя бы
минимальный перерыв, т.е. Шеф может успеть на
j-е (по списку приглашений) после
i-го, если и только если
aj>bi.Напишите программу, помогающую Шефу посетить заседания с как можно
большей суммарной важностью. Если
возможны разные наборы с одинаковой
максимальной суммарной важностью, выбрать
тот, где меньше суммарная длина заседаний.
Технические условия. Программа читает с клавиатуры сначала количество заседаний
N, где 2<=N <= 5 000, затем
N троек (ai, bi, ci).
Гарантированно, что 0 <=ai <
bi < 109, все ci натуральные и их сумма не превышает
109. Программа должна вывести на экран через пробел суммарную
важность и суммарную длительность выбранных заседаний.
