printРабочее место участника

printЗадачи

82. Три робота

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Есть прямоугольное поле размером `N\ times\ M`, разбитое на клетки единичного размера. В некоторых клетках этого поля расположены препятствия, и на них нельзя попасть, а для каждой из остальных клеток известно количество золота, которое в ней находится. У вас есть три робота, изначально они находятся в левом верхнем углу поля, и все они должны добраться до правого нижнего угла поля. За один ход каждый робот может сдвинуться на одну клетку вправо или на одну клетку вниз, если он при этом не выйдет за пределы поля и не попадет на клетку с препятствием. Находясь на определенной клетке, робот забирает из нее все золото. Взятое золото в клетке не восстанавливается, и другие роботы там уже ничего не получат. На одной клетке могут находиться несколько роботов. Когда все роботы добираются в правый нижний угол, подсчитывается суммарное количество золота, собранного ими. Требуется так провести роботов по полю, чтобы максимизировать это суммарное количество золота. Гарантируется, что роботов можно провести из левого верхнего в правый нижний угол.
Ввод
В первой строке входного файла содержится два целых числа `N` и `M` (`2≤N,\ M≤50`). Далее следуют `N` строк, в каждой из которых содержится `M` целых чисел в диапазоне от `-1` до 1000 (числа в строке отделяются пробелами). Число, находящееся в `i`-й строке на `j`-м месте, равно количеству золота в соответствующей клетке поля или `-1`, если в этой клетке находится препятствие. В левом верхнем и в правом нижнем углах поля всегда находится ноль единиц золота.
Вывод
Вывести единственную строку, содержащую максимальное суммарное количество золота, которое могут собрать три робота.

Пример ввода 1

3 3
0 5 7
3 8 6
9 -1 0

Пример вывода 1

29

Пример ввода 2

4 5
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 0

Пример вывода 2

164
loading