K. Маршрут максимальной стоимости
2000 мс · 256 МБ · всё или ничего
В левом верхнем углу таблицы находится черепашка. В каждой клетке записано число. Черепашка перемещается только вправо или вниз и заканчивает маршрут в правом нижнем углу.
Просуммируем числа во всех клетках, через которые проползла черепашка, включая начальную и конечную. Найдите наибольшее возможное значение этой суммы.
В исходной задаче требовалось вывести ещё и сам маршрут, а маршрутов с одинаковой суммой бывает много. Здесь нужна только сумма; маршрут спрашивают в домашней работе, и там для него зафиксировано правило.
Формат ввода
Первая строка содержит числа и ().
Следующие строк содержат по целых чисел от до .
Формат вывода
Одно число — наибольшая возможная сумма.
Примеры
ввод
5 5 9 9 9 9 9 3 0 0 0 0 9 9 9 9 9 6 6 6 6 8 9 9 9 9 9
вывод
74
Войдите, чтобы отправлять решения.