Рассмотрим точку, которая будет покрыта последней. Можно заметить, что в момент, когда все круги оптимального радиуса, есть три случая:

1. Эта точка -- вершина многоугольника и лежит на одной окружности.
2. Эта точка лежит на одной из сторон и на двух окружностях.
3. Это точка пересечения трёх окружностей, и она лежит внутри многоугольника.

Генерируем все точки-кандидаты, для каждой из них проверяем, что она лежит в многоугольнике, и если да, то обновляем ей ответ.

Решение за куб. Идея: для любых трёх непересекающихся подпрямоугольников можно найти разбиение исходного прямоугольника на 3, что наши подпрямоугольники лежат в этих по одному. Так разбить можно принципиально двумя разными способами:

+----+   +--+-+
+----+   |  | |
+----+   +--+-+
+----+   +----+

Насчитаем 6 динамик. Первая -- это dp[i][j]= максимальной сумме на подпрямоугольнике с вершинами в верхнем левом углу и (i, j), следующие 3 -- то же самое с другими углами, следующая -- dp[i][j]= максимальной сумме на подпрямоугольнике, содержащемся в столбцах от i до j, последняя -- то же, но со строками. Легко понять, как через эти динамики посчитать ответ. Динамики считаются так:

Идём по строкам сверху вниз, для каждой пары (i, j) помним минимальную сумму всех чисел на прямоугольнике между этими столбцами, что мы встречали. В итоге для любой тройки $$$(r, c_1, c_2)$$$ мы узнаем максимальную сумму чисел на всех прямоугольниках $$$[x_1, x_2]\times[c_1, c_2]$$$, где $$$x_1 \leqslant x_2 \leqslant r$$$, через это можно посчитать первые 5 динамик, последнюю считаем так же, но для строк.

Не знаю, как объяснить нормально, зашло за 0.3с, а Вы как делали? Там, кажется, байт на 4 степень, судя по тайм лимиту