<PREV Problem:
NEXT>
Solved by 20 users: WsemirZ, Cheryl, wInuX, lutyj, tourist, dan, zloy_mipt, chenxiuwei, KZ, mazahaka, MIKseR, UdH-WiNGeR, defrager, RAVEman, topspin, fetetriste, EAA2008, Dest, LiuChenheng, JohnJones_001.
UserDateAttemptTimeCMSC
Dest10 jul 2010C++400.38614 
RAVEman27 feb 2009C++100.16625 
fetetriste27 dec 2009C++100.62649 
JohnJones_00118 sep 2012C++200.38658 
defrager27 feb 2009C++100.94789 
dan12 sep 2008C++100.11873 
UdH-WiNGeR26 feb 2009Java101.68930 
chenxiuwei31 oct 2008C++300.261017 
lutyj15 aug 2008C++103.891168 
topspin23 jun 2009Kylix200.211200 
Languages
C++
11
Kylix
7
Java
2
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Time Management (Refactoring 2)

Time limit = 5 second(s)

See problem 132.

Now tasks have value. Your program should choose tasks with maximum total value (no need to maximaze number of tasks).

Input First line contains number of tasks N, 0 < N < 10001. Each of next N lines contains four numbers. First two integer numbers from [0, 2000000000] state for beginning and ending of time frame (those are represented in minutes from some fixed moment in time). Third number is 0 (task can be excluded) or 1 (task is mandatory). Fourth number is task value from [0, 10000]. Task's lengths are not less than 20 minutes.

Output First line should contain two integer numbers K and V — number of non-overlapping tasks and maximum total value.

Next K lines should contain description of K chosen tasks. In each line: identifier of a task and shift of that task (integer number from [-10,10]).

All important tasks should be chosen.

If it's not possible, output single line "NO SOLUTION".

Input#1
3
6 31 1 0
20 52 1 0
40 73 1 10000
Output#1
NO SOLUTION 
Input#2
5
0 21 1 0
1 22 1 0
11 32 0 765
41 62 1 872
42 63 1 12
Output#2
NO SOLUTION 
Input#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 
Output#3
4 77
4 -9
3 -8
5 10
6 10
Input#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
Output#4
4 10011
2 2
3 -5
6 6
0 10


Author:
Sanekf
21 May 2008

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 34.231.21.83