Fişierul intrare/ieşire:deal.in, deal.outSursăOJI 2012 clasa a 8-a
AutorEmanuela CerchezAdăugată deMstar_AngelComan Mara Mstar_Angel
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Deal (clasa a 8-a)

Vasilică are la grădiniţă N turnuri cu înălţimile h1, h2, ..., hN. Când aşază în linie nişte turnuri, cel puţin două, astfel încât înălţimile lor să fie în ordine crescătoare, Vasilică spune că a construit un deal. Înălţimea dealului este egală cu înălţimea celui mai înalt turn folosit. Iată, de exemplu, că aşezând în ordine turnurile cu înălţimile 2 4 4 7 9 a format un deal cu înălţimea 9.

Vasilică şi-ar dori să aşeze în linie cele N turnuri, formând o succesiune de dealuri astfel încât suma înălţimilor dealurilor formate să fie maximă.

Cerinţă

Scrieţi un program care, cunoscând înălţimile celor N turnuri, va determina suma înălţimilor dealurilor ce se pot forma aşezând în linie cele N turnuri, maximă posibil.

Date de intrare

Fişierul de intrare deal.in conţine pe prima linie numărul natural N. Pe cea de a doua linie se află N numere naturale separate prin spaţii, reprezentând înălţimile celor N turnuri.

Date de ieşire

Fişierul de ieşire deal.out va conţine o singură linie pe care va fi scris un număr natural reprezentând cerinţa problemei.

Restricţii

  • 2 ≤ N ≤ 100 000
  • 1 ≤ Înălţimile turnurilor ≤ 100 000
  • Dacă după aranjarea turnurilor hi ≤ hi+1 atunci turnurile i şi i+1 fac parte din acelaşi deal.

Exemplu

deal.indeal.outExplicatii
7
10 2 2 2 7 5 2
22
O soluţie posibilă cu suma înălţimilor 22 ar fi:
2 10 2 5 2 2 7
S-au format trei dealuri: 2 10 (cu înălţimea 10) şi 2 5 (cu înălţimea 5) şi 2 2 7 cu înăţimea 7.
Trebuie sa te autentifici pentru a trimite solutii. Click aici