Please help
It looks like n^2 m*t should pass.
The answer for 200 and 35 is the minimum
Of max(sum(bomb in packet), solve(n-packet,34)
That should solve it i guess
Please elaborate your explanation
Time complexity =O(n^2 *m *t)
Let solve(i,j) denote the answer for last i elements and j people
Test case
4 3
10 20 30 40
Start with solve(n=4,m=3)
It is equal to minimum of
Max(10,solve(3,2))
Max(10+20,solve(2,2))
It shouldnt go to solve(1,2) because it is impossible to distribute 1 packet to 2 people
Now we have solve(3,2)
N=3 m=2
20 30 40
Min of
Max(20,solve(2,1))
Max(50,solve(1,1))
Solve(i,1) should just return the sum of the last i elements because only one person is left to receive.
So it is 50
Solve(2,2)
2 2
30 40
This has only one case
Max(30,solve(1,1)) which equals 40
Put these values in the start
Minimum of
Max(10,50)
Max(30,40)
Which equals 40
Ans=40
I got it thanks man.
This problem can also be solved with Time Complexity : O(N*log(Sum))*t sum is sum of all elements.
refer:
since n is small in this problem so nnm*t will give better time complexity