SEQPAR  Partition the sequence
Given an integer sequence containing n elements (numbered from 1 to n), your task is to find the minimum value M so that we can find k + 1 integers 0 = p(0) < p(1) < p(2) < ... < p(k1) < p(k) = n, such that for any i from 0 to k  1, the sum of elements from postition p(i)+1 to postition p(i+1) is not greater than M.
Input
The first line of input contains the number of test cases nTest (1 <= nTest <= 10).
Each test case contains:
The first line contains n, k. (1 <= k <= n <= 15000)
Each of the next n lines contains an integer of the sequence with value range from 30000 to 30000.
Output
For each test case write the minimum number M in a separate line.
Example
Input: 1 9 4 1 1 1 3 2 2 1 3 1 Output: 5
hide comments
Prismatic:
20150715 07:51:10
I used BS + BIT + compress data :D


humble_coder:
20150123 19:54:47
the question basically is to find the minimum value of M such that we can partition the array into k subarrays such that  each subarray's sum <= M 

Dominik Kempa:
20090818 21:29:07
5 is minimal number such that sequence can be partitioned into 4 parts such that sum of each is not greater than 5, this partition is (for example): [1,1,1], [3,2], [2,1], [3,1] Last edit: 20091203 08:19:25 

Frane KurtoviĆ¦:
20090723 12:58:03
Can anyone explain provided test case?

Added by:  Nguyen Dinh Tu 
Date:  20060102 
Time limit:  7.414s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  Viet Nam Olympiad in Informatic 2005, Day I 