← вернуться к уроку · Практика: Динамика по сетке
Самый длинный подъём
8000 мс · 512 МБ · всё или ничего
В клетках поля написаны высоты. Из клетки можно перейти в соседнюю по стороне, если её высота строго больше.
Какой наибольшей длины путь можно пройти? Длина считается числом клеток.
Формат ввода
В первой строке числа и от до . В следующих строках по чисел от до .
Формат вывода
Одно число.
Примеры
ввод
1 1 5
вывод
1
Примечание
Состояние — «длина самого длинного подъёма, начинающегося в этой клетке». Порядок вычисления задаётся высотами: если считать от высоких клеток к низким, все нужные значения окажутся готовы. Рекурсия с запоминанием тоже подошла бы, но на поле в четверть миллиона клеток она упрётся в предел глубины.
Войдите, чтобы отправлять решения.