Elevi Pentru Elevi Arges - XI/XII | Sarituri

În timp ce Victor se plimba prin pădure, i-a fost atrasă atenția de un copil ce se juca pe trotuar.
El sărea de pe primul pătrat, care avea un număr scris cu creta în interior, pe un alt pătrat, cu alt număr scris, și tot așa până la al $N$-lea pătrat, aflat la finalul desenului. Pentru a face jocul mai interesant, bunicul lui i-a dat următoarea provocare:
Acesta a observat fiecare număr $A_i$ aflat pe al $i$-lea pătrat, cu $1 \le i \le N$, și i-a spus că, pornind de pe primul pătrat, la fiecare săritură, îi va da atâtea bomboane cât diferența dintre numărul de pe pătratul pe care a ajuns și numărul de pe pătratul de pe care a sărit, totul la pătrat. Mai formal:
$nr_{bomboane} = (nr_{ajuns} - nr_{sărit})^2$ ,
cu semnificațiile:

• $nr_{bomboane}$ = Numărul de bomboane pe care i le va da bunicul la o săritură
• $nr_{ajuns}$ = Numărul aflat pe pătratul pe care a ajuns
• $nr_{sărit}$ = Numărul aflat pe pătratul de pe care a sărit

Băiatul poate sări doar în față și se poate opri din sărit oricând este mulțumit cu numărul de bomboane obținute.

Cerință

Știind numărul de pătrate, $N$, numerele de pe fiecare pătrat, $A_1$, $A_2$, ..., $A_N$, și că nepotul poate, în orice moment, să sară câte maximum $K$ pătrate, calculați numărul maxim de bomboane pe care le poate obține.

Date de intrare

Pe prima linie a fișierului de intrare sarituri.in se află două numere naturale nenule, $N$ și $K$, cu semnificația din enunț.
Pe a doua linie se află $N$ numere naturale, $A_1$, $A_2$, ..., $A_N$, cu semnificația din enunț.

Date de ieșire

Pe prima linie a fișierului de ieșire sarituri.out se va afișa un singur număr natural, care reprezintă răspunsul la cerința dată.

Restricții și precizări

• $2 \le N \le 10^5$
• $1 \le K \le 10$
• $0 \le A_i \le 10^6$, cu $1 \le i \le N$
• Se acordă 10 puncte din oficiu.

Exemplul 1

sarituri.in

4 1
3 6 1 2

sarituri.out

35

Explicație

Copilul poate sări câte maximum un singur pătrat, deci șirul de sărituri este:
$1 \rarr 2 \rarr 3 \rarr 4$:

Este evident că suma maximă este $(A_2 - A_1)^2 + (A_3 - A_2)^2 + (A_4 - A_3)^2$, relație egală cu:
$(6 - 3)^2 + (1 - 6)^2 + (2 - 1)^2 = 9 + 25 + 1 = 35$.

Exemplul 2

sarituri.in

5 2
2 3 8 7 2

sarituri.out

72

Explicație

Copilul poate sări câte maximum două pătrate, deci săriturile pot fi:

• $i \rarr i + 1$
• $i \rarr i + 2$

Se observă că șirul ce obține suma maximă este:
$1 \rarr 3 \rarr 5$.

Astfel, se obține suma maximă: $(A_3 - A_1)^2 + (A_5 - A_3)^2$, relație egală cu:
$(8 - 2)^2 + (2 - 8)^2 = 36 + 36 = 72$