ZOJ Problem Set - 3399
Here comes the new term. In this new term, there are N new students who enter Nobita's primary school. The president is busy with the classes division. Right now he is considering what is the best way to divide N students into no more than K classes so that they may cause the least amount of unhappiness in total.
But how to define and forecast the unhappiness students will cause in future? That's a question. Fortunately, Doraemon is nearly omnipotent. He tells the president that he can use an integer to describe a student's sentiment index, xi for the i-th student. Let L be the average of xi (i = 1, 2, ..., N). To simplify the problem, if L is not an integer, let it be the floor of itself. If the i-th student is sent into the k-th class, he will cause (xi - L)2 * gk units of unhappiness. Don't worry about the value of gk (k = 1, 2, ..., K), Doraemon can also tell them to the president.
Now it's the president's turn to determine the division. For some special reasons, the division should obey these following rules.
The president can not find out the best division, so he turns to you for help. Remember that the total amount of unhappiness students cause is the sum of unhappiness each student causes. Your job is to figure out the minimum total amount of unhappiness and the best division. To simplify the problem, you are only asked to tell the number of classes K1 and the number of students in the K1-th class T.
There are multiple cases.
For each case, there are three lines. In the first line, there are four integers, N (1 <= N <= 10000), K (1 <= K <= 200), A (1 <= A <= N) and B (A <= B <= N), describe as above. The next line contains N integers, x1, x2, ... , xN (1 <= xi <= 100000). The last line contains K integers, g1, g2, ... , gK (-1000 <= gi <= 1000).
For each case, if there is no solution, output "No solution." in one line; otherwise, output three integers in a single line. The first is the minimum total amount of unhappiness. The second is the number of classes K1 follows, if there are multiple solutions to get the minimum total amount, output the smaller K1. Last is the number of students in the last class T, if there are still multiple solutions, output the smaller T.
There is a blank between cases.
10 3 1 4 16 11 12 13 10 15 16 17 18 14 4 5 1
186 3 4
Author: MO, Luyi
Contest: ZOJ Monthly, September 2010