Polish version    English version  
  O olimpiadzie -> Zadania -> VI OI 1998/1999


 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
VI Olimpiada Informatyczna 1998/99

Zadanie: WOD
Autor: Grzegorz Jakacki
Woda

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.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego WOD.IN rozmiary szachownicy oraz wysokości prostopadłościanów ustawionych na poszczególnych polach,
  • obliczy maksymalną objętość wody, która po deszczu może pozostać w zastoiskach,
  • zapisze wyniki w pliku tekstowym WOD.OUT.

Wejście

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.

Wyjście

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.

Przykład

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.




Wersja do druku