Fişierul intrare/ieşire:profit.in, profit.outSursăinfoarena 2.0
AutorDin FolclorAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test0.05 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Profit

De curând, Don BJ a încheiat un contract de colaborare cu o binecunoscută companie care furnizează energie electrică. Primul lucru pe care îl are de făcut Don BJ este acela de a verifica stâlpii de înaltă tensiune. După o scurtă inspecţie, el a observat că există N stâlpi aşezaţi în linie (numerotaţi de la 1 la N), fiecare având o înalţime dată Ai. Deoarece Don BJ este o persoană cu simţ estetic, el acum doreşte să modifice înalţimile stâlpilor astfel încât, la final, acestea să formeze o secvenţă fie crescătoare, fie descrescătoare. Cu alte cuvinte, Don BJ vrea să creeze o nouă secvenţă B1, B2, .., Bn în care fie B1B2 ≤ .. ≤ Bn, fie B1B2 ≥ .. ≥ Bn.
Costul total de a transforma secvenţa este |A1 – B1| + |A2 – B2| + .. + |An – Bn|. Deoarece Don BJ este un afacerist înnăscut el doreşte ca în final costul total de a aranja stâlpii să fie minim.
Deoarece v-a promis un procent foarte mare din profiturile tuturor afacerilor sale, voi trebuie să calculaţi acest cost minim.

Date de intrare

Pe prima linie a fişierului profit.in se află N, numărul de stâlpi. Pe următoarele N linii se află înălţimile Ai ale stâlpilor de înaltă tensiune (pe linia i+1 se găseşte Ai).

Date de ieşire

Fişierul profit.out trebuie să conţină un singur număr, costul minim pentru a transforma secvenţa din fişierul de intrare într-o secvenţă crescătoare sau descrescătoare.

Restricţii

  • 1 ≤ N ≤ 2000
  • Înălţimile stâlpilor sunt numere naturale din intervalul [0, 109]
  • Don BJ ştie cu siguranţă că rezultatul se încadrează într-un întreg reprezentat pe 32 de biţi

Exemplu

profit.inprofit.out
4
1
5
3
10
2

Explicaţie

Don BJ hotărăşte să aducă stâlpul 2 la înălţimea 4 şi stâlpul 3 la înălţimea 4. Astfel costul total este |5 - 4| + |3 - 4| = 2. Acesta este şi costul minim.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content