Capacidade de Transporte
Você precisa transportar $N$ caixas com pesos dados usando uma esteira transportadora. A esteira realiza uma viagem por vez, sempre carregando as caixas na ordem em que foram fornecidas (sem reordenar).
Cada viagem da esteira carrega um grupo consecutivo de caixas, desde que a soma total dos pesos não ultrapasse a capacidade máxima permitida da esteira.
Seu objetivo é determinar a menor capacidade máxima possível da esteira tal que todas as caixas possam ser transportadas usando no máximo $K$ viagens.
Input
A primeira linha contém dois inteiros $N$ e $K$ $(1 \leq N \leq 10^6,\ 1 \leq K \leq N)$: o número de caixas e o número máximo de viagens permitidas.
A segunda linha contém $N$ inteiros $w_1, w_2, \ldots, w_N$ $(1 \leq w_i \leq 10^9)$: os pesos das caixas, na ordem em que devem ser transportadas.
Output
Um único inteiro representando a menor capacidade máxima necessária da esteira para cumprir o transporte dentro de no máximo $K$ viagens.
5 3 8 1 7 3 9
10
Explanation 1:
A divisão das caixas pode ser feita assim:
* Viagem 1: [8, 1] → soma 9
* Viagem 2: [7, 3] → soma 10
* Viagem 3: [9] → soma 9
Total de 3 viagens, cada uma com soma ≤ 10.
Se tentarmos capacidade menor (ex: 9), serão necessárias mais de 3 viagens.
10 5 9 4 7 19 8 4 20 19 11 10
27