Atenție! Aceasta este o versiune veche a paginii., scrisă la 2016-01-07 15:37:42.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire deal.in, deal.out Sursă OJI 2012 clasa a 8-a
Autor Emanuela Cerchez Adăugată de avatar Mstar_Angel Coman Mara Mstar_Angel
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.$
    h2. Exemplu
deal.in deal.out Explicatii

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii