| РСО-Алания 2018-2023. Избранное |
|---|
| Finished |
Гора представляет собой матрицу $$$n$$$ на $$$m$$$. Строки пронумерованы от $$$1$$$ до $$$n$$$, столбцы — от $$$1$$$ до $$$m$$$. В каждой ячейке находится целое число. Вы хотите спуститься с горы (выйти за пределы матрицы снизу). Вы можете начать с любой ячейки первой строки. Из каждой клетки вы можете попасть в соседние по сторонам клетки (двигаться вверх нельзя). Каждую клетку можно посещать не более одного раза. Красота пути — это сумма всех чисел, клетки которых вы посетили. Ваша задача — посчитать максимальную красоту пути после спуска с горы.
В первой строке даны два натуральны числа через пробел: $$$n, m$$$ $$$(1\leq n, m\leq1500)$$$.
В следующих $$$n$$$ строках даны по $$$m$$$ целых чисел через пробел (по модулю не больше, чем $$$100$$$) — описание матрицы.
В единственной строке выведите ответ на задачу.
3 3 -1 1 -1 -1 1 1 -1 2 3
8
2 2 1 1 2 2
6
3 2 1 -5 1 1 -5 0
3
| Name |
|---|


