Задача №111533. Банкротство
Недавно у градообразующего предприятия города Флатвилля сменилось руководство. Новый генеральный директор не очень-то разбирается в техническом производстве, поэтому заключает все договоры подряд. После этого (чтобы спасти положение) в дело вступает директор по расписаниям, который решает, какие из этих заказов будут выполнены, а за какие придется платить неустойку.
Каждый заказ обладает тремя параметрами: di — максимальный номер дня, к которому этот заказ должен быть выполнен; ai — доход, который получает завод, если выполняет заказ в срок; bi — неустойка, которую выплачивает завод в случае, если заказ не был выполнен к дню di включительно. Нумерация дней ведется со следующего после заключения договоров дня. Известно, что на выполнение одного заказа завод тратит непрерывный отрезок из ровно K дней, причем в один момент времени завод может быть занят только одним заказом.
В итоге перед директором по расписаниям стоит непростая задача: выбрать какие заказы выполнить (и в какое время), а за какие проще сразу заплатить неустойку.
Конкурирующая фирма хочет данное предприятие разорить. У директора конкурирующей фирмы есть возможность перехватить любое число заказов. Все остальные заказы достанутся предприятию (даже если они явно ему не выгодны). Требуется помочь директору конкурирующей фирмы выбрать такое подмножество имеющихся потенциальных заказов для перехвата, чтобы при оптимальной работе директора по расписаниям (то есть при выборе им наилучшей стратегии выполнения оставшихся заказов) доход предприятия был минимальным (он может быть и отрицательным).
В первой строке входного файла записано одно число G — номер группы тестов. Во второй строке задано два числа N и K. Следующие N строк содержат описание заказа: di, ai, bi. Числа K, ai, bi целые положительные и не превосходят 1 000. Числа di целые положительные и не превосходят 100 000.
В первой строке выведите значение искомого дохода (убытка) предприятия. Следующая строка должна содержать ровно N нулей и единиц, разделенных пробелами. Если на i-й позиции стоит 0, это означает, что этот заказ должна перехватить конкурирующая фирма; если же стоит 1, то заказ достанется предприятию.
1
4 1
1 9 9
1 4 4
1 3 3
1 3 3
-2
0 1 1 1
6
8 4
1 10 3
2 10 3
3 10 3
4 10 3
5 8 3
6 7 2
6 5 5
7 6 1
-10
1 1 1 1 1 1 1 1
Тесты состоят из девяти групп.
- Тесты 1–2, из условия, оцениваются в 0 баллов.
- В тестах этой группы 1 ≤ N ≤ 100 000, K = 1, di = 1, ai = bi для всех i. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы 1 ≤ N ≤ 100 000, K = 1, di = 1 для всех i. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы 1 ≤ N ≤ 100 000, ai = bi, di = dj, для всех i, j. То есть все заказы имеют одинаковый срок выполнения, и для всех заказов прибыль равна неустойке. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы 1 ≤ N ≤ 1 000, di = dj, для всех i, j. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы 1 ≤ N ≤ 100 000, di = dj, для всех i, j. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы 1 ≤ N ≤ 15. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы 1 ≤ N ≤ 100, ai = bi. На этой группе будут тестироваться только решения, прошедшие хотя бы одну из групп 1 - 6. Группа состоит из 20 тестов, за каждый тест участник получает либо 0, либо 1 балл. Участник получает за тест 1 балл, если его ответ корректен и никакое другое решение (другого участника или жюри) не находит ответ лучше.
- В тестах этой группы 1 ≤ N ≤ 100. На этой группе будут тестироваться только решения, прошедшие хотя бы одну из групп 1 - 6. Группа состоит из 20 тестов, за каждый тест участник получает либо 0, либо 1 балл. Участник получает за тест 1 балл, если его ответ корректен и никакое другое решение (другого участника или жюри) не находит ответ лучше.