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.