Polish version    English version  
  O olimpiadzie -> Zadania -> IX OI 2001/2002


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
IX Olimpiada Informatyczna 2001/2002

Zadanie: dzi
Autor: Jakub Pawlewicz
Działka

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.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego dzi.in opis pola,
  • wyznaczy działkę o największej powierzchni,
  • zapisze w pliku tekstowym dzi.out powierzchnię wyznaczonej działki.

Wejście

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.

Wyjście

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.

Przykład

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



Wersja do druku