Дан квадрат 15 × 15 клеток, в каждой клетке которого записано целое число. В левом верхнем углу квадрата стоит робот. За один ход робот может переместиться на одну клетку вправо, вниз или по диагонали вправо вниз. Выходить за пределы квадрата робот не может. Необходимо переместить робота в правый нижний угол так, чтобы сумма чисел в клетках, через которые прошёл робот (включая начальную и конечную), была максимальной. В ответе запишите максимально возможную сумму.
Исходные данные записаны в электронной таблице.
Пример входных данных (для таблицы размером 4 × 4):
| 4 | 21 | −36 | 11 |
| 37 | −12 | 29 | 7 |
| −30 | 24 | −1 | −5 |
| 8 | −8 | 9 | 21 |
Для указанных входных данных ответом будет
Найдём максимальную сумму. Для этого найдём максимальную сумму для каждой ячейки таблицы. Для каждой ячейки верхней строки это будет сумма всех ячеек слева от текущей. Для каждой ячейки левого столбца это будет сумма всех ячеек сверху от текущей.
=МАКС(Q2;Q1;R1)+B2
и скопируем эту формулу во все ячейки диапазона R2:AE15. Таким образом,
Ответ: 820.