Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Đurica je pronašao n karata poređanih u niz. Na kartama su zapisani celi brojevi.Datom nizu karata A, Đurica dodeluje vrednost f(A) koja je jednaka sumi razlika vrednostina uzastopnim kartama. Formalno,
f(A) = Σ(Ak + 1 - Ak), k = 1 .. n - 1
gde Ai predstavlja vrednost na i-toj karti u nizu.

Đurica iz niza želi da izbaci najviše K karata. Izbacivanjem nekih m karata, mK, dobija nov niz karata kojem ponovo računa vrednost na opisani način. Od svih mogućih odabira vrednosti m i svih mogućih odabira m karata koje će izbaciti, njega zanima onaj niz karata koji će imati najveću vrednost. Pomozite Đurici i recite mu koliko je ta najveća vrednost. Primetimo da Đurica ni u jednom momentu ne menja raspored karata datih na početku.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu nalaze se celi brojevi n (2 ≤ n ≤ 500.000) i K (0 ≤ Kn - 2). U narednom redu se učitavaju celi brojevi Ai (-1.000.000 ≤ Ai ≤ 1.000.000), u i-tom redu broj Ai.

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu ispisati jedan ceo broj koji predstavlja najveću vrednost niza koju Đurica može da dobije od početnog izbacivanjem najviše K karata.

Primer 1.

standardni ulaz      standardni izlaz
11 4
1 7 2 5 3 8 2 3 6 5 5
        
5

Objašnjenje.

Jedno optimalno rešenje je da se izbacimo 3 karte iz niza. Karte koje treba izbaciti imaju na sebi vrednost 5.

Primer 2.

standardni ulaz      standardni izlaz
3 1
10 9 8
        
-1

Comments

There are no comments at the moment.