|
Пирамида
(Время: 3 сек. Память: 32 Мб Сложность: 83%)
После победы в великой битве Король Ягуар хочет построить пирамиду, которая будет одновременно монументом в честь победы и гробницей для погибших солдат. Пирамида будет построена на поле боя. Она должна иметь прямоугольное основание, состоящее из a столбцов и b строк. Для сохранения останков и оружия павших солдат внутри основания пирамиды будет располагаться небольшая прямоугольная комната, состоящая из c столбцов и d строк.
Архитекторы Короля представили поле боя в виде прямоугольной сетки. Эта сетка состоит из квадратных клеток единичной площади и имеет m столбцов и n строк. Для каждой клетки они измерили ее высоту и получили некоторое целое число.
Основание пирамиды и комната должны покрывать включаемые ими клетки полностью, а их стороны должны быть параллельны сторонам поля боя. Высоты клеток, составляющих комнату, должны остаться неизменными, а высоты всех клеток основания пирамиды будут выровнены с помощью перемещения песка с более высоких клеток на более низкие. В результате этого высота основания пирамиды будет равна среднему арифметическому высот всех его клеток (за исключением клеток комнаты). Архитекторы могут выбрать любое местоположение для комнаты внутри пирамиды, но обязательно оставлять вокруг комнаты стену основания пирамиды толщиной хотя бы в одну клетку.
Помогите архитекторам выбрать наилучшее место для расположения пирамиды и комнаты внутри нее так, чтобы высота основания пирамиды была максимально возможной при заданных размерах.
На рисунке показан пример поля боя, где число в каждой клетке обозначает ее высоту. Клетки, составляющие основание пирамиды, обозначены серым цветом, а белые клетки внутри основания пирамиды соответствуют расположению комнаты. На этом рисунке представлен пример оптимального решения.
Напишите программу, которая по заданным размерам поля боя, пирамиды и комнаты, а также по заданным высотам всех клеток будет находить максимально возможный объем пирамиды (сумму всех высот в клетках, где будет располагаться основание пирамиды).
Входные данные
Первая строка входного файла INPUT.TXT содержит шесть целых чисел: m, n, a, b, c и d (3 ≤ m,n ≤ 1000, 3 ≤ a ≤ m, 3 ≤ b ≤ n, 1 ≤ c ≤ a-2, 1 ≤ d ≤ b-2). Далее идет описание поля боя, состоящее из n строк, каждая из которых содержит m целых чисел от 1 до 100, разделенных пробелами. Эти числа соответствуют высотам клеток в одной строке сетки. Первая из этих строк соответствует верхней строке (строке 1) сетки, а последняя – нижней строке (строке n). При этом m чисел в каждой строке соответствуют высотам клеток этой строки, начиная со столбца 1.
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – максимально возможный объем пирамиды.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 8 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2 | 70 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |