Задача про замок

Добрый вечер) Помогите решить задачку, мне кажется она решается рекурсией, но я не совсем понимаю, как оформить это в коде

В игре «Heroes of Wizardry and Sorcery» игровой мир представляет собой таблицу N × M с квадратными полями, длина сторон которых равна 1. Поля обозначаются (i,j), где i — номер строки, а j — номер столбца. Каждому полю соответствует магическая защита Di,j.

Ваш замок находится на поле (A,B). Вы можете построить защитную ограду в форме прямоугольника, стороны которого проходят по линиям таблицы, при этом замок должен находиться внутри ограды. Пусть верхнее левое поле забора (p,q), правое нижнее (r,s), а длина забора равна l. Тогда защитная сила забора равна Dp,q + Dr,s + l.

Требуется построить забор с максимальной защитной силой.

Первая строка стандартного входа содержит четыре целых числа — количество строк N (1 ≤ N ≤ 1000), количество столбцов M (1 ≤ M ≤ 1000) и координаты A и B — номер строки и столбца вашего замка (1 ≤ A ≤ N, 1 ≤ B ≤ M).
Каждая из последующих N строк содержит по M целых чисел. j-е число в i-й строке задаёт магическую защиту поля Di,j (1 ≤ Di,j ≤ 1000).
Примеры:

Входные данные:
3 3 2 2
8 8 1
7 9 5
3 4 7

Выходные данные:
27

0

eaa, но в гугле россиян пока еще не банили...

0

Я вообще думал решить это через тернарник)

0

Сообщение от Visage__ тернарник

это тернарный(троичный) поиск?

Добавлено через 56 секунд

0

Сообщение от Visage__ Я вообще веб-программист, но меня вынудили это пройти

Ну если фронтенду предлагают задачу для бэкенда, то это действительно странно. Но у каждого свои причуды.
Что за контора?

Добавлено через 9 минут

Сообщение от Red white socks Если же это не максимум, то по крайней мере должно отсечь кучу точек. И перебор по оставшимся.

Все-таки кажется, что этот шаг не понадобится. Ц.ф. - это сумма потенциалов плюс 4, поэтому точки с максимальными потенциалами дают решение.

0

Это не контора, а олимпиада)

0

В наше время участие в олимпиаде было сугубо добровольным делом.

0

Меня записали не особо поведав мне о чем она. Просто сказали, что есть олимпиада, и я в ней участвую

0

Visage__, но читерить (решать чужим умом) вас точно никто не заставляет.

0

аххахаха(

Я мог бы решить это задание, точнее уже решил, но с ограничением по времени справится не могу
Я сюда пришел как раз в поиске сокращенного кода

0

Зачем код сокращать? Тут он как раз увеличится.

1

Сокращать относительно времени выполнения

0

Сообщение от Visage__ Я мог бы решить это задание, точнее уже решил, но с ограничением по времени справится не могу Я сюда пришел как раз в поиске сокращенного кода

Ну так Вам ведь уже подсказали быстрый алгоритм. Левая верхняя клетка (p,q) должна лежать выше и левее замка (a,b) - в красной зоне, она добавит к защите свою магическую защиту и периметр (красные отрезки): D[p,q] + 2(a-p+1) + 2(b-q+1). Таким образом - линейным поиском ищем клетку (p,q) с максимальным этим значением. Аналогично - правая нижняя клетка (r,s) должна лежать правее и ниже замка - в зеленой зоне, она добавляет к защите: D[r,s] + 2(r-a) + 2(s-b). Искать клетки (p,q) и (r,s) можно сразу при чтении входных данных, не заводя память под их хранение. Ответ - сумма двух найденых значений (в синей и красной зоне).

2

Код конечно рабочий, но уже поздно.
Я отправил какое-то решение на 250 баллов из 300.
Думаю, что нормально

0