All submissions for this problem are available.
Team 7 consisting of Naruto, Sasuke and Sakura is the base of the Leaf Village. This team got divided initially but eventually they all came along in the 4th Shinobi World War. They were the only reason for their victory. After their victory, the Leaf Village started to prosper but soon a new problem arose.
The problem was education for The New Generation. There were a total of N students seeking education. Each student has a different chakra level, ith student of which has a chakra level Ai. These students are arranged in the form of an array A, ith element of which denotes the chakra level Ai of the ith student. The Leaf Village administration thought of a method to deal with this education problem which was to divide these students into K non-empty groups (of varying sizes) as currently they had only K teachers available.
Formally, the task is to partition the array A (of chakra levels of students) into exactly K non-empty subarrays. Now the partition should be done in such a way that the sum of the minimum chakra levels of each of the K groups is maximum. As the entire village is busy with the renovation work of the village, so can you help them calculate this maximum sum.
The first line of input contains two space-separated integers N and K denoting the number of students and the number of teachers (or the number of parts into which the array has to be partitioned).
The next line contains N space-separated integers denoting the array A (the array that has to be partitioned into K parts), ith element of which is the chakra level of the ith student.
The output should consist of a single integer corresponding to the answer of the problem.
- 1 ≤ N ≤ 5000
- 1 ≤ K ≤ N
- 1 ≤ Ai ≤ 109
Information to Score Partial Points
- For 5% of the score, it is guaranteed that K = 2 and N ≥ 2.
- For further 5% of the score, it is guaranteed that N ≤ 10.
- For further 10% of the score, it is guaranteed that N ≤ 100.
- For further 15% of the score, it is guaranteed that N ≤ 500.
- For the rest of the 65% of the score, no extra guarantees. That is, N ≤ 5000.
Input: 5 3
1 5 9 2 3 Output: 12
4 5 9 2 3 7
Example case 1. The most optimal way to divide the array into exactly 3 subarrays such that the sum of minimum values of these 3 subarrays is maximum is [1,5],  and [2,3] for which the sum is 1+9+2=12.
Example case 2. The most optimal way to divide the array into exactly 3 subarrays such that the sum of minimum values of these 3 subarrays is maximum is [4,5],  and [2,3,7] for which the sum is 4+9+2=15.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions