L'alpinista fatxenda P78622


Statement
 

pdf   zip

html

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