- Описание
- Отправленные решения
16. Даркстор
Петя стажёр в Яндекс Лавке и ему нужно решить задачу по размещению нового даркстора на карте размером $N$ на $M$, где каждая клетка имеет определенное значение прибыли или убытка. Цель Пети - выбрать непустую прямоугольную область на карте, где разместить даркстор будет наиболее выгодно.
Формат ввода
Первая строка содержит два числа $N$ и $M$ - размеры карты. ($1 \le N, M \le 200$)
Следующие $N$ строк содержат $M$ чисел $x_{ij}$ $(1 \le i \le N, 1 \le j \le M, -10^5 \le x_{ij} \le 10^5)$ - значение прибыли или убытка для Яндекса в каждой клетке.
Формат вывода
Выведите одно число - максимальную возможную прибыль.
Ограничения
Ограничение времени
1 с
Ограничение памяти
512 МБ
Пример 1
Ввод
2 2
-2 1
2 4
Вывод
6
Пример 2
Ввод
3 3
1 0 4
2 -1 1
-1 5 2
Вывод
13