Robar casas
Estás planeando asaltar casas en una calle. Hay
n casas y conoces de antemano cuánto dinero puedes robar de cada una. El sistema de alarma avisa automáticamente a la policía si dos casas adyacentes son robadas la misma noche.¿Cuál es la cantidad máxima de dinero que podrías obtener en una sola noche sin que te atrapen?
Entrada
La primera línea de la entrada contiene un solo número entero
n (1 ≤ n ≤ ).La segunda línea contiene
n números enteros separados por espacios (1 ≤ ≤ ), que representan la cantidad de dinero que se puede robar de cada casa.Salida
El programa debe imprimir la máxima cantidad de dinero que se puede obtener sin ser descubierto.
Ejemplos
Entrada | Salida |
4
1 2 5 1 | 6 |
5
3 17 12 3 7 | 24 |
Explicación
- 1 + 5
- 17 + 7 (saltando algunas casas en medio)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB