Hemodinamică

Time limit: 1s Memory limit: 64MB Input: Output:

Se dau două matrice binare AA și BB, fiecare cu NN linii și MM coloane. Definim distanța Hamming dintre două submatrice determinate de colțurile stânga-sus (x1,y1)(x_1, y_1) și dreapta-jos (x2,y2)(x_2, y_2) ca fiind numărul de poziții (i,j)(i, j) cu proprietatea că x1ix2x_1 \leq i \leq x_2, y1jy2y_1 \leq j \leq y_2 și Ai,jBi,jA_{i,j} \neq B_{i, j}.
Vom nota cu H(x1,y1,x2,y2)H(x_1, y_1, x_2, y_2) distanța Hamming dintre cele 22 submatrice determinate de colțurile stânga-sus (x1,y1)(x_1, y_1) și dreapta-jos (x2,y2)(x_2, y_2) în matricele AA și BB.

Cerință

Să se calculeze

1x1x2N[1y1y2MH(x1,y1,x2,y2)]\sum_{1 \leq x_1 \leq x_2 \leq N} \left[ \sum_{1 \leq y_1 \leq y_2 \leq M} H(x_1, y_1, x_2, y_2) \right]

Date de intrare

Pe prima linie se vor găsi numerele NN și MM. Pe următoarele NN linii se află câte MM cifre binare, reprezentând elementele matricei AA. Pe următoarele NN linii se află câte MM cifre binare, reprezentând elementele matricei BB.

Date de ieșire

Se va afișa un singur număr, 1x1x2N1y1y2MH(x1,y1,x2,y2)\sum_{1 \leq x_1 \leq x_2 \leq N} \sum_{1 \leq y_1 \leq y_2 \leq M} H(x_1, y_1, x_2, y_2).

Restricții și precizări

  • 1N,M1 0001 \leq N, M \leq 1 \ 000;
  • Ai,j,Bi,j{0,1},i{1,2,,N},j{1,2,,M}A_{i,j}, B_{i, j} \in \{0, 1\}, \forall i \in \{1, 2, \dots, N\}, \forall j \in \{1, 2, \dots, M\};
  • Pentru 3030 de puncte, 1N,M501 \leq N, M \leq 50;
  • Pentru restul de 7070 de puncte, nu există restricții suplimentare.

Exemplu

stdin

3 3
1 0 1
1 1 0
0 0 1
0 0 1
1 0 1
0 1 1

stdout

49

Explicație

De exemplu, pentru submatricea determinată de punctele (1,2)(1, 2) și (3,3)(3, 3), distanța Hamming este 33, deoarece A2,2B2,2A_{2,2} \neq B_{2,2}, A2,3B2,3A_{2,3} \neq B_{2,3} și A3,2B3,2A_{3,2} \neq B_{3,2}. Suma distanțelor Hamming pentru toate submatricele determinate de două perechi de puncte este 4949.

Log in or sign up to be able to send submissions!