spoj
Задача
F
Наименование
park

Условие

ПАРК 
---
Започва ремонт в градския парк, който има форма на квадрат с дължина страната n. Ще бъдат покрити с нова настилка алеите, ще бъдат сменени пейките, ще има нов детски кът, ново осветление и др. Но най-атрактивното е построяването на водна каскада. Каскадата ще бъде правоъгълна и трябва да е с най-голямата възможна площ. Страните на каскадата са успоредни на страните на парка. На строителите е дадена карта на парка (виж фигурата, където n = 8), на която има защриховани клетки. В тези клетки има паметници на културата, които не трябва да бъдат унищожавани. Напишете програма park, която намира максималната площ на каскадата, без да се налага унищожаването на паметниците на културата. 
 
Вход 
---
От първия ред на стандартния вход се въвежда едно цяло число n – дължината на страната на парка. От следващите n реда се въвеждат по n на брой нули и единици на всеки ред, разделени с по един интервал. 1 съответства на защрихована клетка, а 0  – на празна. 

Изход 
---
На един ред на стандартния изход програмата трябва да изведе единствено цяло число – максималната площ на каскадата 

Ограничения 
---
Вaшата програма ще бъде оценена с 16 тестови примера в 12 от които 1 ≤ n ≤ 50. Всеки от тях носи по 8 точки. В 4 теста 50 < n < 200 и всеки от тях носи по 1 точка.

Примерен вход	
8 
0 0 1 0 1 0 0 0 
0 1 1 0 1 1 0 0 
1 1 1 0 0 0 0 1 
1 1 0 0 0 0 1 1 
0 0 0 0 0 0 0 1 
0 0 0 0 0 0 1 1 
0 0 1 0 0 0 0 0 
0 1 0 1 0 1 0 1	

Примерен изход
15

Пояснение: 
---
В дадения пример най-големият възможен правоъгълник е съставен от стълбове с номера от 4-ти до 6-ти, редове с номера от 3-ти до 7-ми и има лице, съставено от 3 х 5 квадратчета.

« Предходна страница Решение Въпрос