<ПРЕД Задача:
СЛЕД>
Задачу решили 20 пользователей: WsemirZ, Cheryl, wInuX, lutyj, tourist, dan, zloy_mipt, chenxiuwei, KZ, mazahaka, MIKseR, UdH-WiNGeR, defrager, RAVEman, topspin, fetetriste, EAA2008, Dest, LiuChenheng, JohnJones_001.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Time Management (Refactoring 2)

Time limit = 5 секунд(ы)

См. задачу 132.

Теперь у задач есть ценность. Нужно набрать задач на максимальную суммарную ценность (максимизировать количество задач не нужно).

Вход. Первая строка содержит количество задач N, 0 < N < 10001. Каждая из следующих N строк содержит четыре числа. Первые два числа из отрезка [0, 2000000000] соответствуют началу и концу временного промежутка времени. Третье число равно 0 (задачу можно исключить) или 1 (задача является обязательной).

Четвёртое число равно ценности задачи и принадлежит отрезку [0, 10000]. Длительности задач больше 20.

Выход. Первая строка должна содержать два целых числа K и V — количество задач, которые решают задачу и их суммарная стоимость.

В следующих K строках должны быть перечислены заявки. В каждой строке необходимо указать индекс взятой заявки и её временной сдвиг.

Все обязательные задачи должны быть включены в ответ.

Если все обязательные задачи не могут быть взяты без перекрытия, то необходимо вывести одну строку "NO SOLUTION".

Вход#1
3
6 31 1 0
20 52 1 0
40 73 1 10000
Выход#1
NO SOLUTION 
Вход#2
5
0 21 1 0
1 22 1 0
11 32 0 765
41 62 1 872
42 63 1 12
Выход#2
NO SOLUTION 
Вход#3
7
56 98 0 10
30 66 0 21
1 30 0 3
37 58 1 1
6 38 0 4
40 62 1 29
62 85 0 43 
Выход#3
4 77
4 -9
3 -8
5 10
6 10
Вход#4
7
66 98 1 3
30 66 0 1
1 30 0 5
37 59 1 3
6 38 0 2
40 62 0 6
48 70 0 10000
Выход#4
4 10011
2 2
3 -5
6 6
0 10


Автор:
sanekf
21 мая 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 18.208.202.194