| Fişierul intrare/ieşire: | oo.in, oo.out | Sursă | Stelele Informaticii 2003, clasele 9-10 |
| Autor | Osman Ay | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20096 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
Oo
Fermierul Ion are o ferma de forma circulara, unde cresc N gaini. Ferma a fost impartita in N sectoare, numerotate de la 1 la N, astfel incat oricare doua sectoare avand numere consecutive sunt adiacente (se afla unul langa altul). In plus, primul si ultimul sector sunt adiacente. In fiecare sector se afla cate o gaina, iar aceasta depune un anumit numar de oua in fiecare zi. Dupa ce gainile depun ouale, fermierul Ion doreste sa le adune, pentru a le manca. Deoarece fermierul este foarte lacom, de fiecare data el alege doua sectoare adiacente din care aduna ouale simultan. Din pacate, din cauza lacomiei sale, gainile din sectoarele vecine cu cele doua alese se sperie si devin violente, motiv pentru care fermierul nu mai poate aduna ouale din aceste sectoare. In exemplul din problema, daca fermierul aduna simultan ouale din sectoarele 1 si 2, el nu va mai putea aduna ouale din sectoarele 3 si 10.
Cerinta
Determinati numarul maxim de oua pe care le poate aduna fermierul Ion, in urma aplicarii strategiei sale lacome.
Date de intrare
Fisierul de intrare oo.in contine pe prima linie numarul de sectoare in care este impartita ferma (si, implicit, numarul de gaini). Pe urmatoarea linie se afla N numere intregi din intervalul [0,100], reprezentand numarul de oua depuse de fiecare gaina, in ordinea sectoarelor in care se afla acestea.
Date de iesire
In fisierul oo.out veti afisa numarul maxim de oua pe care le poate aduna fermierul Ion.
Restrictii
- 2 ≤ N ≤ 100 000
Exemplu
| oo.in | oo.out |
|---|---|
| 10 3 4 0 1 0 6 7 1 2 1 | 20 |
Explicatie
Fermierul poate aduna ouale din sectoarele 2 si 3 (4+0), 6 si 7 (6+7) si 9 si 10 (2+1).
