Rapinare le case
Stai progettando di rapinare delle case in una strada. Ci sono
n case e conosci l’ammontare di denaro che potresti ottenere da ognuna di esse. Il sistema di allarme contatta automaticamente la polizia se vengono rapinate due case adiacenti nella stessa notte.Qual è il massimo importo che potresti ottenere in una sola notte senza essere scoperto?
Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ ).La riga successiva contiene
n interi separati da uno spazio (1 ≤ ≤ ), ossia la quantità di denaro che si può rubare da ogni casa.Output
Il programma deve stampare il massimo importo ottenibile senza farsi scoprire.
Esempi
Input | Output |
4
1 2 5 1 | 6 |
5
3 17 12 3 7 | 24 |
Spiegazione
- 1 + 5
- 17 + 7 (saltando alcune case intermedie)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB