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
Dest`10 jul 2010`C++400.38614
RAVEman`27 feb 2009`C++100.16625
fetetriste`27 dec 2009`C++100.62649
JohnJones_001`18 sep 2012`C++200.38658
defrager`27 feb 2009`C++100.94789
dan`12 sep 2008`C++100.11873
UdH-WiNGeR`26 feb 2009`Java101.68930
chenxiuwei`31 oct 2008`C++300.261017
lutyj`15 aug 2008`C++103.891168
topspin`23 jun 2009`Kylix200.211200
 C++ 11 Kylix 7 Java 2
` >  >  >  >  >  >  >  >  >  > `

## Time Management (Refactoring 2)

Time limit = 5 second(s)

See problem 132.

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

 © acm.mipt DevGroupThe page was generated in 190ms