Fişierul intrare/ieşire:tablou.in, tablou.outSursăAlgoritmiada 2019 Runda PreOJI
AutorAlexandru PetrescuAdăugată dealexpetrescuAlexandru Petrescu alexpetrescu
Timp execuţie pe test1.3 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tablou

Marcel a facut rost de un tablou, codificat printr-o matrice de N linii si M coloane, in fiecare celula aflandu-se o cifra, reprezentand o culoare. Astfel, tabloul T are pe linia l (numerotate de sus in jos de la 1 la N) si coloana c (numerotate de la stanga la dreapta de la 1 la M) culoarea codificata prin cifra T[l][ c ].

K fete nastrusnice isi fac cate o copie a tabloului si apoi coloreaza cu cate o culoare 0 ≤ cul[i] ≤ 9 pe o submatrice, adica toate celulele de linie l si coloana c cu lin1[i] ≤ l ≤ lin2[i] si col1[i] ≤ c ≤ col2[i] capata culoarea cul[i], iar celelalte celule isi pastreaza culoarea tabloului initial, unde prin i am considerat-o pe a i-a fata.

Neomodernistii isi pun intrebarea, cat este de valoros fiecare dintre noile tablouri? Au convenit sa calculeze valoarea unui tablou ca suma dereglarilor dintre el si toate tablourile noi, inclusiv el insusi. Dereglarea dintre tabloul A si tabloul B este definita asa: Pentru toate pozitiile (a, b) din A si toate pozitiile (p, q) din B, se aduna la dereglare A[a][b] - B[p][q], adica diferenta ( nu in modul) dintre cifrele care reprezinta culorile celor doua celule alese.

Date de intrare

Fişierul de intrare tablou.in contine, pe prima linie, numerele N de linii, respectiv M de coloane ale tabloului ce urmeaza sa fie descris pe urmatoarele N linii, printr-un sir de M cifre nedespartite prin vreun spatiu. Pe linia N + 2 se afla numarul K de fete. Pe urmatoarele K linii apar cate 5 numere lin1[i] col1[i] lin2[i] col2[i] cul[i], descriind felul in care va arata tabloul obtinut de a i-a fata.

Date de ieşire

În fişierul de ieşire tablou.out se vor afla K numere pe linii separate, reprezentand valoarea numerica a fiecarui tablou, in ordinea in care au fost descrisi in input. Adica al i-ulea numar din ouput corespunde celui de-al i-ulea tablou nou din input.

Restricţii

  • 1 ≤ N, M ≤ 3.000
  • 1 ≤ K ≤ 100.000
  • 1 ≤ lin1[i] ≤ lin2[i] ≤ N
  • 1 ≤ col1[i] ≤ col2[i] ≤ M
  • Pentru 10% din teste, se cunoaste, in plus, ca N, M, K ≤ 11
  • Pentru inca 20% din teste, se cunoaste, in plus, ca N, M, K ≤ 200
  • Pentru inca 30% din teste, se cunoaste, in plus, ca K ≤ 1.000
  • Veţi primi rezultatele evaluării doar pe fişierul de intrare din exemplu. Acestea nu vor afecta scorul problemei, având punctajul asociat 0.
  • Se garanteaza ca raspunsul se incadreaza pe tipuri de date de 64 de biti cu semn.

Exemplu

tablou.intablou.out
4 5
01234
12345
23456
34567
11
1 1 3 3 2
1 2 4 5 8
2 3 2 3 5
3 5 4 5 6
2 1 3 5 3
3 2 4 3 0
3 3 4 4 9
4 3 4 5 5
3 4 4 4 4
1 1 1 1 0
3 4 4 5 7
-1160
12920
-720
-1380
-2260
-4680
2360
-1820
-1820
-1160
-280
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?