4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Задача B. Витя - черепашка-ниндзя

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Витя готовится стать членом команды нового поколения черепашек-ниндзя. Ему осталось пройти самое важное испытание - решить задачу Донателло. Донателло дал Вите таблицу состоящую из $n$ строк и $m$ столбцов. В каждой клетке таблицы написано целое число. Изначально, на клетке в левом верхнем углу таблицы находится фишка. Фишку можно двигать либо на одну клетку вниз либо на одну клетку вправо и только если на соответствующей стороне существует другая клетка. Фишку двигают пока она не окажется на клетке в правом нижнем углу таблицы. Результатом пути называется сумма чисел на клетках по которым прошла фишка (включая начальную и последнюю клетку). Вите нужно найти путь с максимальным результатом. Узнав об этом испытании, Леонардо решил что Витя очень легко справится с таким заданием (при его то потенциале). Поэтому, он решил усложнить задачу. На этот раз, перед тем как двигать фишку, Витя может попросить Леонардо сделать некоторое (возможно нулевое) количество вертикальных и горизонтальных разрезов на таблице своими катанами. Резать можно только по краям клеток и можно считать что катаны Леонардо всегда длиннее сторон таблицы (то есть таблица режется от края до края). В итоге, таблица разделяется на секции. Теперь фишка стоит на левой верхней секции и может двигаться на секцию вниз или на секцию вправо пока не окажется на правой нижней секции. Результатом такого пути называется сумма чисел на клетках секций по которым прошла фишка (включая начальную и последнюю секцию). Помогите Вите разрезать таблицу и найти путь так, чтобы максимизировать результат.

Формат входного файла

В первой строке даны два целых числа $n$ и $m$ ($1 <= n <= 1000$, $1 <= m <= 50$). В следующих $n$ строках даны по $m$ целых чисел -- $j$-тое число на $i$-той строке $a_{i, j}$ ($-10^{9} <= a_{i, j} <= 10^9$) является числом на клетке в $i$-той строке и $j$-том столбце таблицы.

Формат выходного файла

Выведите одно целое число -- максимальный результат пути которого можно достичь, после совершения некоторого (возможно нулевого) количества разрезов на таблице.

Система оценки

Данная задача содержит $8$ подзадач, в которых выполняются следующие ограничения:

1. Тесты из условия. Оценивается в $0$ баллов.
2. $a_{i, j} > 0$. Оценивается в $5$ баллов.
3. $a_{i, j} < 0$. Оценивается в $12$ баллов.
4. $n = 2$. Оценивается в $10$ баллов.
5. $n, m <= 10$. Оценивается в $10$ баллов.
6. $n, m <= 40$. Оценивается в $20$ баллов.
7. $n <= 100$, $m <= 50$. Оценивается в $21$ балл.
8. Исходные условия задачи. Оценивается в $22$ балла.

Примеры:

Вход

2 2
2000 600
0 4

Ответ

2604

Вход

4 5
4 23 -10 -2 3
0 1 7 -3 0
2 3 -3 30 1
4 -17 8 0 5

Ответ

78

Замечание

Пояснение ко второму примеру.

( Rauan Omarov )