03/04/2025 12:00:51

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

Задачи

2491. Двумерные массивы-13

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

Дана матрица

$a$ размером

$n\ times\ m$ .

Напишите программу для нахождения подматрицы с максимально возможной суммой элементов.

Для решения задачу используйте формулу включения-исключения и вспомогательную матрицу

$b$ размером

$(n+1)\ times\ (m+1)$ , в которой элемент

$b_{i+1,j+1}$ содержит сумму элементов подматрицы

$a_{0..i,0..j}$ , а элементы

$b_{0,i}=b_{j,0}=0$ .

Первая строка ввода содержит два целых числа

$n$ и

$m$ (

$1\ ≤\ n,\ m\ ≤\ 100$ ). Следующие

$n$ строк содержат

$m$ чисел в диапазоне от –100 до 100.

Вывести одно целое число – максимально возможную сумму элементов подматрицы.

Пример ввода

3 4
-1 -1 -10 -2
4 -2 10 -8
-9 3 -1 -6

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

Подматрица с возможной суммой элементов:
4 –2 10