Fişierul intrare/ieşire:	ksecv.in, ksecv.out	Sursă	Selectie echipe ACM ICPC, UPB 2008
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.15 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ksecv

Se da o secventa S ce contine N numere intregi pozitive. Pozitiile pe care se afla aceste numere sunt numerotate de la 1 la N. O subsecventa S[i:j] (1≤i≤j≤N) a unei secvente S este o secventa alcatuita din elementele de pe pozitiile i, i+1, ..., j din cadrul secventei S. Vom spune ca o pozitie x apartine unei subsecvente S[i:j], daca i≤x≤j.
Costul unei subsecvente S[i:j] este egal cu elementul maxim din cadrul acesteia. O K-impartire a unei secvente S este o multime de K subsecvente disjuncte (din punct de vedere al pozitiilor din S) ale lui S, care, impreuna, acopera intreaga secventa S (adica fiecare pozitie din S apartine exact unei subsecvente). Costul unei K-impartiri este egal cu suma costurilor celor K subsecvente.

Determinati o K-impartire de cost minim a unei secvente S date.

Date de intrare

Prima linie a fisierului de intrare ksecv.in contine doua numere intregi, separate printr-un spatiu: N si K. A doua linie contine N numere intregi, reprezentand, in ordine, elementele secventei S date. Doua numere consecutive din cadrul secventei vor fi separate printr-un spatiu.

Date de iesire

In fisierul de iesire ksecv.out veti afisa costul minim al unei K-impartiri a secventei S date in fisierul de intrare.

Restrictii

• 1 ≤ N ≤ 100.000
• 1 ≤ K ≤ min{N, 100}
• Orice element al secventei este un numar intreg din intervalul [0,10.000.000].

Exemplu

Cum se trimit solutii?