Fişierul intrare/ieşire:operatii.in, operatii.outSursăpreONI 2008 Runda 2
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.35 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Operatii

Consideram un vector nul cu N elemente ( fiecare element este egal cu 0 ). Asupra vectorului se efectueaza un numar de operatii de forma: se selecteaza doi indici i si j, i ≤ j, si se incrementeaza cu o unitate toate elementele din vector dintre pozitiile i si j inclusiv.
Dandu-se un vector v cu N elemente, sa se precizeze care este numarul minim de operatii de tipul celei precizate mai sus care trebuiesc efectuate pentru a ajunge de la vectorul nul la vectorul v.

Date de intrare

Fisierul de intrare operatii.in contine pe prima linie numarul N. Cea de a doua linie contine N numere naturale, reprezentand elementele vectorului v.

Date de iesire

In fisierul de iesire operatii.out se va scrie pe prima linie numarul minim de operatii care trebuiesc efectuate asupra vectorului nul pentru a obtine vectorul v.

Restrictii

  • 1 ≤ N ≤ 1 000 000
  • Fiecare numar din v este mai mic sau egal cu 100 000
  • Se considera ca primul element al oricarui vector este situat pe pozitia 1
  • Pentru 10% din teste, N ≤ 10
  • Pentru 30% din teste, N ≤ 1 000
  • Pentru 40% din teste se garanteaza ca rezultatul nu va depasi 3 000

Exemplu

operatii.inoperatii.out
7
0 2 2 1 0 1 2
4

Explicatie

vectoroperatia efectuata
0 0 0 0 0 0 0i = 2, j = 4
0 1 1 1 0 0 0i = 2, j = 3
0 2 2 1 0 0 0i = 6, j = 7
0 2 2 1 0 1 1i = 7, j = 7
0 2 2 1 0 1 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content