Задача D. По законам жанра
Задачу добавил: alef
Успешно сдано решений: 114
Ещё министр экономики Калистрат рассказал, что планируется тщательным образом освещать строительство спортивно-туристического комплекса. Съёмочные группы уже подали заявки, в какие дни они хотели бы приехать на объект. Список заявок — это список дней a1, a2, ..., an (a1 < a2 < ... < an), занумерованных от первого дня строительства.
Известно, что съёмочной группе, посетившей объект в день #ai, потребуется wi дней (не включая день посещения) на подготовку материала. Как только группа подготовит материал, он немедленно будет показан в эфире. Если в некоторый день будет готово несколько материалов, они могут быть показаны в произвольном порядке, который определяется выпускающим редактором и повлиять на который нельзя.
С точки зрения Калистрата, материал, отснятый в день #ai, будет иметь интересность ci. Калистрат хочет, чтобы в эфир материалы попали в том порядке, в каком они снимались, и ради этого готов отказать каким-то съёмочным группам. При этом он хочет, чтобы суммарная интересность материалов, показанных в эфире, была максимально возможной.
Ваша задача — определить, какова может быть максимально возможная суммарная интересность показанных материалов (и заявки каких групп при этом нужно удовлетворить).
В первой строке содержится целое число n (1 ≤ n ≤ 1000) — количество заявок съёмочных групп.
Во каждой из последующих n строк содержится по три целых числа ai, wi и ci (1 ≤ ai, wi, ci ≤ 105, i = 1, 2, ..., n) — день, в который хотела бы приехать съёмочная группа, подавшая заявку #i; количество дней, которое ей потребуется на обработку материала, интересность этого материала с точки зрения Калистрата.
Гарантируется, что a1 < a2 < ... < an.
В первой строке выведите целое число — максимально возможную суммарную интересность показанных материалов.
Во второй строке выведите целое число m — количество заявок съёмочных групп, которые для этого потребуется удовлетворить.
В третьей строке выведите через пробел m чисел — номера заявок, которые потребуется удовлетворить.
Если существует несколько возможных наборов заявок, выведите любой из них.
Подзадача 1 (30 баллов)
n ≤ 20
Баллы начисляются в случае прохождения всех тестов группы.
Подзадача 2 (до 70 баллов)
n ≤ 1000
Баллы начисляются в случае прохождения всех тестов группы.
По запросу сообщается результат проверки на каждом тесте.
8
1 7 4
4 2 2
5 3 5
8 5 3
11 1 2
14 6 4
16 3 4
19 1 4
18
5
2 3 4 7 8
Поясним приведённый пример.
Удостовериться в том, что данная последовательность заявок приводит к ответу 18, несложно. Обратим, однако, внимание на то, что данная последовательность является единственно возможной. В частности, заявка #7 не может быть заменена на заявку #6: обе они имеют равные значения интересности, но материал, снятый по заявке #6, будет готов в день #20, и в этот же день будет готов материал, снятый по заявке #8.
Поскольку нет никаких гарантий, что материал, снятый по заявке #6 окажется в эфире раньше снятого по заявке #8, выбрать их одновременно нельзя.