| Fişierul intrare/ieşire: | inundatie.in, inundatie.out | Sursă | Grigore Moisil 2011, Clasa 9-a |
| Autor | Perticas Catalin | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Inundatie
Mitruţ, motanul încălţat, vă dă harta unui oraş fermecat de furnici care are forma unei matrice dreptunghiulare cu N linii şi M coloane. Se poate considera că în fiecare căsuţă (i, j) a matricei, cu i=1,2,…,N şi j=1,2,…,M, se află un bloc al cărui număr de etaje ei,j se cunoaşte. Fiindcă şi Mitruţ a gustat din prăjitura magică, a dobândit puteri supranaturale şi îşi pune acum problema pedepsirii furnicilor lacome prin inundarea oraşului. Astfel, Mitruţ îşi pune Q întrebări precum care este numărul total de locuinţe afectate dacă pompează apă în oraş până la etajul eqk (k=1,2,…,Q)?
Cerinţă
Răspundeţi la cele Q întrebări puse de Mitruţ.
Date de intrare
Pe prima linie a fişierului de intrare inundatie.in se află numerele naturale N şi M. Urmează N linii cu câte M numere naturale fiecare. Numărul j de pe linia i reprezintă câte etaje are blocul situat în căsuţa (i, j) pe harta lui Mitruţ. Următoarea linie conţine numărul natural Q, iar ultimele Q linii din fişier conţin fiecare câte un număr natural ce reprezintă întrebarea pusă de Mitruţ.
Date de ieşire
Fişierul de ieşire inundatie.out trebuie să conţină răspunsurile la cele Q întrebări puse de Mitruţ.
Restricţii
- 1 ≤ N, M ≤ 300
- 1 ≤ Q ≤ 100 000
- 0 ≤ ei,j ≤ 1 000 000 000 (i=1,2,…,N, j=1,2,…,M)
- 0 ≤ eqk ≤ 1 000 000 000 (k=1,2,…,Q)
- Pentru 30% din teste: Q ≤ 1000 şi N, M ≤ 50.
- Fiecare etaj al unui bloc adăposteşte o singură locuinţă.
- Numerotarea etajelor începe de la 1.
- Dacă ei,j = 0 atunci în căsuţa (i, j) nu există un bloc.
- Pentru o întrebare eqk trebuie inundate în întregime toate locuinţele care se află la un etaj mai mic decât eqk, în timp ce acele locuinţe care se află la un etaj mai mare sau egal trebuie să rămână neatinse.
Exemplu
| inundatie.in | inundatie.out |
|---|---|
| 3 3 7 3 5 0 2 0 5 0 2 4 2 4 1 5 | 6 16 0 19 |
Explicaţie
Pentru prima întrebare a lui Mitruţ vor fi inundate toate locuinţele situate la etaje mai joase decât etajul 2. Sunt 6 astfel de locuinţe (locuinţele de la etajul 1 din blocurile situate în (1,1), (1,2), (1,3), (2,2), (3,1), (3,3)).
