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(k-1) < 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.
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.
For each test case write the minimum number M in a separate line.
Input: 1 9 4 1 1 1 3 2 2 1 3 1 Output: 5
I used BS + BIT + compress data :D
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
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: 2009-12-03 08:19:25
Can anyone explain provided test case?