There are n numbers A0,A1,...,An-1. Now you have to divide them no more than k group so that each group contains consecutive numbers (ex: you can divide 5 numbers in groups (A0, A1) (A2, A3, A4), but you cannot divide them in groups (A0, A1, A4) (A2, A3) ) so that the maximum sum S of numbers in certain group is minimum.
Please calculate the minimum value of S and there are how many ways can the n numbers be grouped so that S is minimum.
There is a number of inputs.(at most 10)
There are two lines in each input. The first line have two number n and k. The second line have n number A0,A1,...,An-1
1<= n <= 50000, 1 <= k <= 1000
0 <= Ai <= 20000
For each input, please print two number denoting the minimum value of S and the number of way that S is minimum(the second number may be very large, so you must print answer mod 10007).
10 6 3 2 1 3 5 8 3 2 1 2 3 3 1 1 10
8 31 10 2
Migrated from old NTUJ.
uva 11299
| No. | Testdata Range | Score |
|---|