Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2491. Двумерные массивы-13
Учебные задачи: двумерные массивы| 01/09/2007 | Основы программирования. Двумерные массивы (13) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
Пример вывода
12
4 –2 10
