[BOJ 8851] Zalew

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 128M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

Ten Wincenty to dopiero oryginał! - pomyślał pan Józef, znany rolnik i hodowca, sąsiad pana Wincentego. Oddał mi spory kawałek swojego ogrodu żeby mieć więcej czasu na rozrywki! Niektórym, to tylko zabawa w głowie, a tu pracować trzeba! </p>

Dla pana Józefa potrzeba rozrywki jest uczuciem zupełnie obcym. Od lat w pocie czoła buduje dobrobyt swojego gospodarstwa i nie zamierza przestawać. Zupełnie niedawno na przykład postanowił poszerzyć swoją działalność o hodowlę ryb - szczupaków i karasi. Wybrał odpowiednie miejsce na staw hodowlany i obmyślił każdy szczegół budowy. Właśnie otrzymał pocztą pozwolenie na budowę, więc przyszedł czas na przejście do czynów.

Pan Józef poszedł do przeznaczonego na staw prostokątnego zagłębienia terenu. Umieścił pompę w najniższym punkcie działki i już miał ją włączyć, kiedy przypadkowo spojrzał na stojącą obok śliwę. Była wprawdzie niemal całkowicie ogołocona z liści, ale było w niej coś, co obiecywało moc owoców wraz z nadejściem kolejnego lata.

Żal byłoby zmarnować te drzewa po tylu wspólnie spędzonych latach (i tylu wysokogatunkowych śliwkach - co jeśli podniosą ceny śliwek w skupie?) - Pan Józef postanowił tak dobrać ilość wody, żeby żadne drzewo owocowe nie zostało zalane, a staw był jak największy.

Jak duży staw uda mu się w ten sposób stworzyć?

(w zadaniu pomijamy stanowisko przeróżnych urzędów, którym zapewne nie spodoba się zmiana planu zatwierdzonego w pozwoleniu na budowę)

입력 형식

W pierwszej linii wejścia znajdują się dwie liczby naturalne N i M ( 1 <= N,M <= 1000 ) - długość i szerokość działki przeznaczonej na staw. Następnie podawany jest opis N*M pól działki w N kolejnych liniach, z których każda składa się z M liczb całkowitych o wartości bezwzględnej <= 10000.</p>

Wartość bezwzględna każdej z tych liczb oznacza wysokość działki w odpowiadającym polu. Liczby ujemne oznaczają pola, w których rosną drzewa owocowe. Liczba 0 oznacza miejsce, w którym znajduje się pompa - gwarantujemy, że będzie tylko jedno takie pole. Każde pole działki ma kształt kwadratu o boku długości 1. Pompowana woda rozlewa się zgodnie z prawami grawitacji, przez wspólny bok sąsiadujących pól (nigdy przez wspólny róg!).

출력 형식

Maksymalna powierzchnia stawu pana Józefa.

예제 입력

4 4
2 3 2 -4
-1 4 0 1
4 1 2 2
2 3 2 -4

예제 출력

7

Comments

There are no comments at the moment.