L'alpinista fatxenda P78622
Un alpinista farà un viatge a un sistema muntanyós amb n pics. Cada dia estarà al costat d’un pic d’alçada ai, i haurà de decidir si escalar-lo o no. Però, com que és un fatxenda, després d’escalar un pic d’una certa alçada no en voldrà escalar cap d’alçada més petita. Quina és la màxima suma d’alçades que podrà escalar?
Entrada
L’entrada consisteix en diversos casos, cadascun amb n, seguida de les n alçades en ordre de visita, totes entre 1 i 109. Suposeu 1 ≤ n ≤ 105.
Sortida
Per a cada cas, escriviu la màxima suma d’alçades possible.
Observació
Podeu obtenir 30 punts resolent casos on n ≤ 100, i uns altres 30 punts resolent casos on ai ≤ 100.
Public test cases
Input
1 42 4 8 2 7 4 8 70 60 50 50 50 100 80 90 3 999999999 1000000000 1000000000
Output
42 9 320 2999999999
Information
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++ Python