Задача E. Любитель искусства (Школьный этап 2015 - 2016)
Задачу добавил: alef
Успешно сдано решений: 48
Товарищи A и B решили прогуляться по центральной аллее парка. Аллея является излюбленным местом выступления многих уличных артистов.
Будем представлять аллею отрезком прямой; в момент времени t = 0 товарищи A и B находятся в начале аллеи — в точке x = 0. На преодоление единицы расстояния они тратят ровно одну единицу времени.
Выступления уличных артистов проходят только в точках с целочисленными координатами, при этом артист #j приходит в точку xj, в которой он будет выступать, в момент времени sj. Затем он показывает несколько выступлений, последнее из которых начинается в момент времени fj. Будем считать, что каждое выступление продолжается одну единицу времени.
Товарищ A, как правило, с интересом относится к таким выступлениям. А вот товарищ B полагает, что во время прогулки куда интереснее общаться друг с другом.
Поэтому товарищи A и B достигли следующей договорённости. Они пойдут по центральной аллее от начала до конца. Если товарищ A пожелает остановиться и послушать выступление какого-либо артиста, то они остановятся и посмотрят ровно одно его выступление, после чего отправятся дальше. Заметим, что товарищ B соглашается слушать ровно одно выступление в одной точке, и даже если товарищи посмотрели последнее выступление одного артиста, после которого его тут же сменит другой артист, смотреть следующее выступление они не останутся.
Товарищ A знает, какое удовольствие cj он получит от просмотра выступления артиста #j. Он хочет получить максимальное суммарное удовольствие от прогулки. Ваша задача — определить, какое максимальное суммарное удовольствие он может получить и выступления каких артистов он при этом должен посмотреть.
В первой строке содержится целое число n (1 ≤ n ≤ 1000) — количество уличных артистов.
В каждой из следующих n строк содержится по 4 целых числа xj, sj, fj, cj (0 ≤ xj ≤ 105, 0 ≤ sj ≤ fj ≤ 105, 1 ≤ cj ≤ 1000) — координата точки, в которой будет выступать артист #j, время начала его выступлений, время, в которое он начнет последнее выступление, а также удовольствие, которое от его выступления может получить товарищ A.
Гарантируется, что если xk1 = xk2, то либо fk1 < sk2, либо fk2 < sk1.
В первой строке выведите максимальное суммарное удовольствие, которое может получить товарищ A.
Во второй строке выведите целое число m — количество артистов, выступления которых он посмотрит.
В третьей строке выведите m целых чисел — номера артистов в том порядке, в котором он будет их смотреть.
Если существует несколько вариантов ответа — выведите любой.
2
1 1 2 10
2 1 2 11
11
1
2
3
1 1 2 6
2 2 3 8
3 3 4 13
21
2
2 3