Teile das Array mit einer minimalen Summe
Gegeben sind
n ganze Zahlen und eine ganze Zahl k. Dabei soll das Array in k zusammenhängende Abschnitte aufgeteilt werden, sodass die größte Summe eines dieser Abschnitte so klein wie möglich ausfällt.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n (1 ≤ n ≤ ) und k (1 ≤ k ≤ n).In der nächsten Zeile folgen die durch Leerzeichen getrennten Zahlen ( ≤ ≤ ).
Ausgabe
Das Programm soll die kleinstmögliche maximale Summe eines Teilarrays ausgeben.
Beispiele
Eingabe | Ausgabe |
5 2
1 2 3 6 2 | 8 |
5 3
1 2 10 3 2 | 10 |
Erklärung
[1 2 3] [6 2]⇒ Die maximale Teilsumme beträgt 6 + 2 = 8
[1 2] [10] [3 2]⇒ Die maximale Teilsumme beträgt 10
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB