Задача K. Максимальная сумма ≡
| Автор: | Седьмая Всероссийская Командная олимпиада школьников по программированию | Ограничение времени: | 2 сек | |
| Входной файл: | max.in | Ограничение памяти: | 64 Мб | |
| Выходной файл: | max.out |
Условие
Сегодня на страницах газеты "Математический досуг" была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из m строк и n столбцов. В каждой ячейке таблицы записано некоторое целое число.
Для решения головоломки требуется найти такой невырожденный прямоугольник с вершинами в центрах ячеек таблицы, и сторонами, параллельными сторонам таблицы, чтобы сумма чисел, записанных в ячейках на границе получившегося прямоугольника, была максимальна.
Безуспешно потратив несколько часов на решение головоломки, Саша решил написать программу, которая сделала бы это за него. Но и тут его постигла неудача. Теперь ему ничего не остается, как обратиться за помощью к вам.
Напишите программу, которая по заданной таблице найдет искомый прямоугольник.
Формат входного файла
На первой строке входного файла записаны два целых числа m и n. Далее следует описание таблицы - m строк, каждая из которых содержит по n целых чисел ai,j.Формат выходного файла
На первой строке выходного файла выведите целое число s - максимальную сумму чисел на границе искомого прямоугольника. На второй строке выведите четыре натуральных числа: x1, y1, x2, y2 - координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь x - номер строки, а y - номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.Ограничения
2 ≤ m, n ≤ 300; − 104 ≤ ai,j ≤ 104Примеры тестов
| № | Входной файл (max.in) |
Выходной файл (max.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|