IX Olimpiada Informatyczna 2001/2002
|
Zadanie: dzi
|
Autor: Jakub Pawlewicz
|
Zawody II stopnia, dzień pierwszy |
Plik źródłowy: | dzi.??? (np. pas, c, cpp) |
Plik wejściowy: | dzi.in |
Plik wyjściowy: | dzi.out |
Dane jest pole w kształcie kwadratu o boku n. Pole jest podzielone na n2 kwadratów o boku 1. Każdy kwadrat jest albo użytkowy, albo nieużytkowy. Na polu wyznaczamy działkę. Ma ona kształt prostokąta i może się składać wyłącznie z kwadratów użytkowych. Powierzchnia działki jest równa polu odpowiadającego jej prostokąta. Szukamy działki o jak największej powierzchni.
Napisz program, który:
W pierwszym wierszu pliku tekstowego dzi.in znajduje się jedna liczba całkowita n, 1 <= n <= 2000. W kolejnych n wierszach opisane są kwadraty tworzące kolejne rzędy pola. Każdy z tych wierszy zawiera n liczb, 0 lub 1, pooddzielanych pojedynczymi odstępami; opisują one kolejne kwadraty w rzędzie --- 0 oznacza kwadrat użytkowy, a 1 nieużytkowy.
Twój program powinien zapisać w pierwszym i jedynym wierszu pliku tekstowego dzi.out jedną liczbę całkowitą --- największą powierzchnię działki. W przypadku, gdy wszystkie kwadraty są nieużytkowe i nie ma żadnej działki, Twój program powinien dać odpowiedź 0.
Dla pliku wejściowego dzi.in:
5 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0
poprawną odpowiedzią jest plik wyjściowy dzi.out:
9