Lavoro di squadra#10401
Per la sua festività preferita, Farmer John vuole inviare regali ai suoi amici. Dato che non è molto bravo a incartare i regali, vuole arruolare l'aiuto delle sue mucche. Come si potrebbe immaginare, nemmeno le mucche sono molto brave a incartare regali — una lezione che Farmer John sta per imparare a sue spese.
Le mucche di Farmer John sono disposte in fila, comodamente numerate da a in ordine. La mucca ha un livello di abilità nell'incartare regali pari a s_i. Questi livelli di abilità possono variare considerevolmente, quindi FJ decide di suddividere le sue mucche in squadre. Una squadra può essere composta da un qualsiasi gruppo di al massimo mucche consecutive, e nessuna mucca può appartenere a più di una squadra. Poiché le mucche imparano l'una dall'altra, il livello di abilità di ogni mucca in una squadra può essere elevato al livello di abilità della mucca più abile in quella squadra.
Aiuta FJ a determinare la massima somma possibile dei livelli di abilità che può ottenere formando le squadre in modo ottimale.
La prima riga contiene due interi e k~(1 \le n \le 10^4, 1 \le k \le 10^3). Ciascuna delle successive righe contiene il livello di abilità di una mucca, nell'ordine in cui le mucche sono disposte. Ogni livello di abilità è un intero positivo non superiore a 10^5.
Stampa un intero — la massima somma possibile dei livelli di abilità che FJ può ottenere suddividendo le mucche in squadre di mucche consecutive.
In questo esempio, la soluzione ottimale è raggruppare le prime mucche e le ultime mucche, lasciando la mucca di mezzo in una squadra da sola (si ricordi che sono permesse squadre con meno di mucche). Di conseguenza, i livelli di abilità delle mucche diventano , , , , , , , la cui somma è .
Esempio 1