VI Olimpiada Informatyczna 1998/99
|
Zadanie: WOD
|
Autor: Grzegorz Jakacki
|
Etap III, dzień drugi | 22 kwietnia 1999 |
Plik źródłowy: | WOD.??? (np. pas, c, cpp) |
Plik wykonywalny: | WOD.exe |
Plik wejściowy: | WOD.in |
Plik wyjściowy: | WOD.out |
Na prostokątnej szachownicy składającej się n*m pól ustawiono n*m prostopadłościanów --- na każdym polu jeden prostopadłościan. Podstawa każdego prostopadłościanu pokrywa się z jednym polem szachownicy i ma powierzchnię jednego cala kwadratowego. Prostopadłościany na sąsiednich polach ściśle przylegają do siebie i nie tworzą żadnych szczelin. Na tę konstrukcję spadł ulewny deszcz. W niektórych miejscach utworzyły się zastoiska wody.
Napisz program, który:
W pierwszym wierszu pliku wejściowego WOD.IN są zapisane dwie dodatnie liczby całkowite n i m, 1 <= n <= 100, 1 <= m <= 100. Są to rozmiary szachownicy. W każdym z kolejnych n wierszy znajduje się m liczb całkowitych z przedziału [1..10000]. i-ta liczba w j-tym wierszu jest wyrażoną w calach wysokością prostopadłościanu stojącego na przecięciu i-tej kolumny i j-tego wiersza szachownicy.
Twój program powinien zapisać w pierwszym i jedynym wierszu pliku wyjściowego WOD.OUT jedną liczbę całkowitą równą maksymalnej objętości wody (wyrażoną w calach sześciennych), która może zebrać się w zastoiskach konstrukcji.
Dla pliku wejściowego WOD.IN
3 6 3 3 4 4 4 2 3 1 3 2 1 4 7 3 1 6 4 1
poprawną odpowiedzią jest plik wyjściowy WOD.OUT
5
Poniższy rysunek przedstawia szachownicę po deszczu (widok z góry). Liczba w lewym górnym rogu pola oznacza wysokość prostopadłościanu. Szare pola oznaczają zastoiska. Liczba w prawym dolnym rogu szarego pola oznacza wysokość słupa wody na tym polu.