Экзаменационный (типовой) материал ЕГЭ / Информатика / 18 задание / 24

Дан квадрат 15×15 клеток, в каждой клетке которого записано целое число. В левом нижнем углу квадрата стоит робот. За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Необходимо переместить робота в правый верхний угол так, чтобы полученная сумма была максимальной. В ответе запишите максимально возможную сумму.

Исходные данные записаны в электронной таблице. Пример входных данных (для таблицы размером 4 × 4):

Для указанных входных данных оптимальным маршрутом будет путь по клеткам 7, 9, 70, 26, 50, 89, 37. Итоговая сумма равна 7 + 9 + 70 + 50 + 89 = 225. Числа 26 и 37 не включаются в сумму, так как 26 < 70 и 37 < 89.