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 | Coman Mara • Mstar_Angel |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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 |
---|---|---|