120 - ZOJ Monthly, September 2012 - J
Sleeper has a trouble planning his schedule recently, partly because he wants to watch the UEFA European Championships, partly due to the Topcoder's and the Codeforces' contests. So he wrote a list of the following events' starting time, ending time and values. Apparently, some of the events have conflicting time schedules, so he has to decide whether he should attend an event or not.
What's more, Sleeper has an extremely accurate biological clock, after he stays awake for t time units, he will suffer more and more every time unit from this point to a limit of l time units' length, when he will fall asleep immediately. However he cannot fall asleep before t time units. Sleeper will wake up exactly after k + dt time units. (Here, dt is the extra time units he stays awake last night after the usual t time units.)
Sleeper wants to sleep well and enjoy his life the most, so he comes to you for help. Write a program to calculate the maximum satisfaction value he can get from the following events. Sleeper stays awake for at least t time units and at most t + l time units once, then he has to go to sleep. If he stays awake for t + dt time units he suffer a total extra-staying-awake-time penalty of dt2(dt>0) to his sum of the event values. When Sleeper is awake and have nothing to do, unless he has been awake for more than or exactly t time units, he cannot go to sleep. The final value is the sum value of the events' values minus the extra-staying-awake-time penalty described above.
The first line of the input is an integer c, which is the number of test cases.
Your output should be exactly c lines, each line with an integer number representing the maximum final value.
2 3 16 8 4 0 4 10 3 5 28 4 18 21 3 16 8 4 26 30 10 29 31 28 30 43 21
In the first case, Sleeper should stay awake for 16 time units and finish the event with value of 28 points. Choosing the first and the third event will get 10 + 21 - 2 * 2 = 27 points, which is a less effective choice.
Author: GONG, Yuan