Fişierul intrare/ieşire:oo.in, oo.outSursăStelele Informaticii 2003, clasele 9-10
AutorOsman AyAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.1 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inoo.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content