Suddividere l'array minimizzando la somma massima
Dati
n interi e un intero k, occorre suddividere l’array in k parti contigue in modo che la somma massima fra queste parti sia la più piccola possibile.Input
La prima riga dell’input contiene due interi
n (1 ≤ n ≤ ) e k (1 ≤ k ≤ n).La riga successiva contiene
n interi separati da spazio, ossia ( ≤ ≤ ).Output
Il programma deve stampare la somma massima di una parte (sottoarray) che risulti la più piccola possibile.
Esempi
Ingresso | Uscita |
5 2
1 2 3 6 2 | 8 |
5 3
1 2 10 3 2 | 10 |
Spiegazione
[1 2 3] [6 2]⇒ la somma massima del sottoarray è 6 + 2 = 8
[1 2] [10] [3 2]⇒ la somma massima del sottoarray è 10
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB