Sereja and Stones
All submissions for this problem are available.
Sereja has N boxes and M stones. There is a parameter energy associated with each empty box, denoted by Ei. He wants to move each stone into some box. After moving all the stones into the boxes, he wants to compute the total energy of box/stone system. For that he believes that a contribution of box into energy of the system can be computed as follows. If box i contains s stones and there are total k boxes out there containing more than s stones, then contribution of box i into the system of energy will be given by Ei × k.
Sereja wants the box/stone system to be most stable, i.e. it should have least possible energy. Find out minimum possible energy of this system.
First line of the input contains an integer T denoting the number of test cases. T tests follow.
First line of each test case contains two space separated integers N and M.
Next line contains N space separated integers denoting the array E.
For each test case output a single integer corresponding to the answer of the problem.
- 1 ≤ T ≤ 7
- 7 ≤ N, M ≤ 77777
- 7 ≤ E[i] ≤ 77
- Subtask #1: (20 points) 7 ≤ N ≤ 77, 7 ≤ M ≤ 777
- Subtask #2: (30 points) 7 ≤ N, M ≤ 777
- Subtask #3: (50 points) original constraints
Input: 2 2 4 7 8 4 6 7 7 10 10 Output: 0 21
In test case 1, there are 2 boxes and 4 stones. The energy of two empty boxes are 7 and 8 respectively. You can put 2 stones into each of the box. Contribution of both the boxes into the energy of the system will be zero. So, the answer will be zero.
In test case 2, there are 4 boxes and 6 stones. You can distribute the stones into boxes as follows, [0, 2, 2, 2]. Contribution of the first box into total energy will be equal to 7 * 3 and that of rest of the boxes will be zero. So, overall energy will be 21. You can enumerate all possible distributions of the stones into boxes and see that you can't obtain a system with less energy than this.
|Tags||dynamic-programming, medium, oct16, sereja|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.