Solución a “Pista”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 14
Autor: Miguel Covarrubias
Fuente: Codeforces

Este problema es una ligera modificación del Let’s Play Osu! que apareció en la ronda 146 en Codeforces. La solución explicada la pueden encontrar en el editorial.

Para N \le 10 se pueden checar todas las 2^N configuraciones de pistas. Para N \le 1000 funciona una dinámica O(N^2), donde los estados son (posición, altura/profundidad que se lleva hasta el momento).

Les dejo la implementación de DiegoRoque como un muy buen ejemplo de una solución a este problema.