Легенда

Подзадача 1. Энергию можно добывать не только из солнца, ветра или течения рек, но даже из падающих капель дождя. Гипотез на этот счёт много, и для проверки одной из них, а именно испытания экспериментальной дождевой электростанции юным учёным нужно выбрать подходящий участок местности, где осадков больше всего. Они нашли подходящий массив в тропиках и имеют на руках информацию о среднегодовой норме осадков.   

Эта информация представлена картой, поделённой на секторы, для каждого из которых указана норма осадков. Карта имеет размер 200 на 200 секторов. Известно, что учёным нужно выбрать на этой карте участок размером 5 на 5 секторов с максимальной суммарной нормой осадков. Помогите им выполнить необходимые вычисления.

Входной формат: двухмерная матрица 200 на 200 из вещественных чисел, перечисленных по строкам через пробел. Вот так:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Выходной формат: два целых числа через пробел, координаты X (по горизонтали) и Y (по вертикали вниз) левого верхнего углового сектора будущего участка. Координаты нумеруются с нуля!

Если несколько участков одинаково подходят по увлажнению, выведите лексикографически минимальную пару координат. То есть из двух пар координат берётся та, где первая координата меньше, при равных первых — вторая. Например, (2, 5) лучше, чем (2, 7), но (1, 8) лучше обеих этих пар. 

Time Limit: 1 секунда

Memory Limit: 256 MB

Напишите программу. Тестируется через stdin → stdout.

Подзадача 2. Задача остаётся та же (в том числе ограничение по времени), но теперь матрица имеет размер 400 на 400 секторов, а требуемый участок — 100 на 100 секторов.

Time Limit: 1 секунда

Memory Limit: 512 MB

Напишите программу. Тестируется через stdin → stdout.


Видео-разбор


Последнее изменение: Monday, 19 September 2022, 12:38