АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

171. Матрица

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Дана матрица, составленная из неотрицательных целых чисел, имеющая N строк и M столбцов. Необходимо найти в ней подматрицу с максимальной суммой граничных элементов. Элемент матрицы считается граничным, если он находится в первой или последней строке или в первом или последнем столбце.

Первая строка входного файла содержит целые числа N и M (2 <= NM <= 200). Затем идёт N строк по M чисел в каждой. Числа в строке разделены пробелом. Гарантируется, что каждый элемент матрицы не превосходит 106.

Первая строка выходного файла должна содержать значение суммы граничных элементов в найденной подматрице. Во второй строке выведите через пробел координаты левого верхнего и правого нижнего углов найденной подматрицы. Первой координатой элемента является строка, а второй столбец. Строки нумеруются от 1 до N сверху вниз, столбцы от 1 до M слева направо. Если подходящих подматриц несколько, выведите любую.

Пример

STDIN

STDOUT

4 5
1 8 1 1 1
1 1 1 9 1
1 1 9 1 1
0 1 1 1 0
  
33
1 1 3 4
  

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / IX Межвузовская олимпиада 2006 /
171. 172. B - 2-10 173. C - Расстановка минусов 174. D - Выполнимость
 
время генерации 0.093 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.