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 $latex N \le 10$ se pueden checar todas las $latex 2^N$ configuraciones de pistas. Para $latex N \le 1000$ funciona una dinámica $latex 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.