Assaltar casas
Está a planear assaltar casas numa determinada rua. Existem
n casas, e sabe a quantia de dinheiro que pode roubar de cada uma delas. O sistema de alarme avisa automaticamente a polícia se duas casas vizinhas forem assaltadas na mesma noite.Qual é o valor máximo que pode obter numa só noite sem ser apanhado?
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ).A linha seguinte contém
n inteiros separados por espaço, (1 ≤ ≤ ), que representam a quantia de dinheiro possível de roubar em cada casa.Saída
O programa deve imprimir o montante máximo que pode ser obtido sem ser apanhado.
Exemplos
Entrada | Saída |
4
1 2 5 1 | 6 |
5
3 17 12 3 7 | 24 |
Explicação
- 1 + 5
- 17 + 7 (ignorando algumas casas pelo meio)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB