Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | volum.in, volum.out | Sursă | ONI 2014, clasele 11-12 |
| Autor | Radu Stefan Voroneanu | Adăugată de |  Tudor Varan •tudorv96 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Volum
K.L. 2.0 şi-a dorit o piscină pe un grid A cu N linii şi M coloane. Cum K.L. 2.0 nu a fost foarte inspirat, el a uitat să îşi niveleze terenul înainte de a construi piscina, astfel încât fiecare celulă de coordonate (i, j) a gridului are o înalţime Ai,j (1 ≤ i ≤ N şi 1 ≤ j ≤ M). La un moment dat începe o ploaie puternică, care umple piscina cu apă. După terminarea ploii, K.L. 2.0 se întreabă câtă apă are în piscină.
Dintr-o celulă apa se varsă în celulele vecine cu care are o latură comună şi care au înălţimea strict mai mică decât celula curentă. Apa de pe marginea piscinei se scurge în exterior.
Cerinţă
Pentru N, M şi gridul A date, să se determine volumul de apă care a rămas în piscină.
Date de intrare
Fişierul de intrare volum.in conţine pe prima linie două numere naturale N şi M, reprezentând dimensiunile gridului, iar pe fiecare dintre următoarele N linii se află câte M numere, reprezentând înălţimile terenului, separate prin câte un spaţiu.
Date de ieşire
În fişierul de ieşire volum.out conţine un singur număr, reprezentând volumul de apă care a rămas în piscină.
Restricţii
- 3 ≤ N, M ≤ 752
- 0 ≤ Ai,j ≤ 109 + 2
- Pentru 30% din punctaj, 3 ≤ N, M ≤ 82.
- Pentru 40% din punctaj, 0 ≤ Ai,j ≤ 103 + 2.
- Volumul apei este suma unităţilor de apă care rămâne în celulele piscinei.
Exemplu
| volum.in | volum.out |
|---|---|
| 3 3 2 2 2 2 0 2 2 2 2 | 2 |
| 3 3 3 3 3 3 0 2 3 3 3 | 2 |
| 5 5 2 2 3 3 3 2 2 3 1 3 2 3 1 3 3 2 2 3 2 2 2 2 2 2 2 | 4 |
Explicaţie
In primul exemplu rămân după ploaie două unităţi de apă în celula cu înălţimea 0. Nu pot rămâne 3 unităţi, deoarece o unitate s-ar scurge prin una din cele 4 celule vecine în exteriorul piscinei.
In al doilea exemplu rămân după ploaie două unităţi de apă în celula cu înălţimea 0. Nu pot rămâne 3 unităţi, deoarece o unitate s-ar scurge prin celula vecină cu valoarea 2 în exteriorul piscinei.
In al treilea exemplu rămân după ploaie câte două unităţi de apă în celulele cu înălţimea 1. Nu pot rămâne câte 3 unităţi. De exemplu, din celula (2,4) apa se poate scurge în celula (2,5) şi apoi în exterior, respectiv din celula (3,3) în şirul de celule (4,3) - (5,3) şi apoi în exterior.
