Optimize

All submissions for this problem are available.
Shrema loves dresses and she has a number of clothes kept in her different wardrobes. Today she has to go for a date with her boyfriend,
so she is searching for a particular type of dress which is stored in one of her wardrobes.
Each wardrobe is of varying capacity and the wardrobes are placed next to one another in a single line .
For searching her favorite dress, Shrema has assigned N number of workers.
She does not want the workers to come in each others way neither does she want the dress to get intermixed with one another
so she has decided to partition the total number of wardrobes among the workers and assign a specific set of wardrobes to each worker.
The set of wardrobes are made in such a way that each worker has atleast 1 wardrobe to search in.
Or in other words we can say Shrema wants to divide the wardrobes into N sections (where N is the number of workers) so that every
wardrobe that the ith worker looks through is earlier in the line than every wardrobe that the jth worker has to look through, for i < j.
Shrema now has decided to partition the wardrobe so as to minimize the maximum number of dresses that a worker would have to look
through.
Input
First line of input contains t : no. of test cases. Then t test cases follows:
Each test case contain n : Number of wardrobes. Then in the next line :
N numbers separated by space denoting number of dress in a wardrobe.
w : Number of workers.
Output
Maximum number of dresses that a worker will have to look through to find the dress in an optimal partitioning of the wardrobe..
Constraints
1 <= t <= 1000
2 <= n <= 1000
No of dresses in a wardrobe is not greater than 1000.
1 <= w <= n
Example
Input: 3 9 10 20 30 40 50 60 70 80 90 3 4 50 50 50 50 2 6 1 1 1 1000 1 1 3 Output: 170 100 1000
Explanation
Example case 1. Suppose there were three workers and nine wardrobes with the following number of dress:
10 20 30 40 50 60 70 80 90
She will divide up the wardrobes into the following sections:
10 20 30 40 50  60 70  80 90
The worker assigned to the first section would have to look through 150 dresses.
The worker assigned to the second section would have to search through 130 dresses, and the last worker would filter through 170 dresses.
In this partitioning, the maximum number of dresses that a worker looks through is 170,i.e.,no other partitioning has less than 170 dresses.
Author:  pacific35 
Tags  pacific35 
Date Added:  8102015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 