| Fişierul intrare/ieşire: | operatii.in, operatii.out | Sursă | preONI 2008 Runda 2 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | operatii.out |
|---|---|
| 7 0 2 2 1 0 1 2 | 4 |
Explicatie
| vector | operatia efectuata |
|---|---|
| 0 0 0 0 0 0 0 | i = 2, j = 4 |
| 0 1 1 1 0 0 0 | i = 2, j = 3 |
| 0 2 2 1 0 0 0 | i = 6, j = 7 |
| 0 2 2 1 0 1 1 | i = 7, j = 7 |
| 0 2 2 1 0 1 2 | |
