Dividir o array com a soma mínima
Dado
n inteiros e um inteiro k, é necessário dividir o array em k partes contíguas de modo que a soma máxima de cada subarray seja a menor possível.Entrada
A primeira linha de entrada contém dois inteiros
n (1 ≤ n ≤ ) e k (1 ≤ k ≤ n).A linha seguinte contém inteiros separados por espaço ( ≤ ≤ ).
Saída
O programa deve imprimir a menor possível soma máxima de um subarray.
Exemplos
Entrada | Saída |
5 2
1 2 3 6 2 | 8 |
5 3
1 2 10 3 2 | 10 |
Explicação
[1 2 3] [6 2]⇒ a soma máxima do subarray é 6 + 2 = 8
[1 2] [10] [3 2]⇒ a soma máxima do subarray é 10
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB