All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Packers N' Movers
Tag(s):

Dynamic Programming, Medium

Problem
Editorial
Analytics

Agon Packers and Movers specialize in moving large number luggages from one place to another.

The luggages are packed by the Packers, and after they're done with the job, the Movers take over.

First, the Packers put the packages they have packed in a single line, one behind the other, and then the Movers come one by one to pick the packages. A Mover can come only once, can only pick the first few packages in the line, and then take them with him. He might also choose not to pick any. Another Mover comes, and repeats the process, till all the packages are taken. The Movers need to carry of all the packages.

The Movers are a friendly lot, and care about each other - so their goal is to minimize the maximum load that any Mover gets.

  • You are given the number of movers M in the first line.
  • The next line contains the number of packages P.
  • The next line contains the weight of the P package (in Kilograms) in order - first weight representing of first package in the line, separated by space.

You need to print the maximum load any mover carries in the best possible case, in accordance with their goal.

Constraints:

  • \(1 \le M \le 15\)
  • \(1 \le P \le 250\)
  • Weight of each Package (W): \(1 \le W \le 10000\)

Examples:
1)
INPUT
5 5 1 1 1 2 1

OUTPUT
2

Explanation: There are 5 movers, and doesn't matter what the split is, one mover needs to carry at least 2 kilograms

2)
INPUT
2 4 5 10 21 20

OUTPUT 36

Explanation: \(36\) is the best case among all the splits possible (happens when the first guy picks 5, \(10\) and \(21\))

SAMPLE INPUT
2
5
200 25 974 564 429
SAMPLE OUTPUT
1199
Time Limit: 5,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

CodeNation

Challenge Name

CodeAgon (Internship Challenge)

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?