Diviser le tableau pour minimiser la somme maximale
Étant donnés
n entiers et un entier k, vous devez diviser ce tableau en k segments contigus de sorte que la somme maximale d'un sous-tableau soit la plus petite possible.Entrée
La première ligne de l'entrée contient deux entiers
n (1 ≤ n ≤ ) et k (1 ≤ k ≤ n).La ligne suivante contient les entiers , séparés par des espaces ().
Sortie
Le programme doit afficher la somme maximale d'un sous-tableau la plus petite possible.
Exemples
Entrée | Sortie |
5 2
1 2 3 6 2 | 8 |
5 3
1 2 10 3 2 | 10 |
Explication
[1 2 3] [6 2]⇒ la somme maximale d'un sous-tableau est 6 + 2 = 8
[1 2] [10] [3 2]⇒ la somme maximale d'un sous-tableau est 10
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB