Dividir el arreglo con una suma mínima
Dado un conjunto de
n enteros y un entero k, se pide dividir el arreglo en k partes contiguas de forma que la suma máxima de subarreglo sea lo más pequeña posible.Entrada
La primera línea de la entrada contiene dos enteros
n (1 ≤ n ≤ ) y k (1 ≤ k ≤ n).La siguiente línea contiene
n enteros separados por espacios ( ≤ ≤ ).Salida
El programa debe imprimir la suma máxima de subarreglo que resulte lo más pequeña posible.
Ejemplos
Entrada | Salida |
5 2
1 2 3 6 2 | 8 |
5 3
1 2 10 3 2 | 10 |
Explicación
[1 2 3] [6 2]⇒ la suma máxima de subarreglo es 6 + 2 = 8
[1 2] [10] [3 2]⇒ la suma máxima de subarreglo es 10
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB