Fişierul intrare/ieşire:inundatie.in, inundatie.outSursăGrigore Moisil 2011, Clasa 9-a
AutorPerticas CatalinAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Inundatie

Mitruţ, motanul încălţat, vă dă harta unui oraş fermecat de furnici care are forma unei matrice dreptunghiu­lare 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.ininundatie.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)).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content