== include(page="template/taskheader" task_id="matrice") ==
Poveste si cerinta...
Se considera o matrice binara B (cu valori 0 sau 1) cu N linii si M coloane, liniile si coloanele fiind numerotate de la 1 la N, respectiv de la 1 la M.
Matricea B este generata dupa regula Bij = Ri xor Cj, unde R si C sunt vectori binari de lungime N, respectiv M.
Numim dreptunghi de colturi (x1,y1) (x2,y2) cu x1≤x2 si y1≤y2, multimea elementelor Bij cu x1≤i≤x2 si y1≤j≤y2. Aria unui astfel de dreptunghi este (x2-x1+1)*(y2-y1+1).
h2. Cerinta
Determinati numarul maxim de elemente egale cu 0 intr-un dreptunghi a carui arie este exact A, precum si numarul de dreptunghiuri pentru care se obtine acest numar maxim.
h2. Date de intrare
...
Fisierul de intrare matrice.in contine pe prima linie numerele naturale N, M, A separate prin câte un spatiu. A doua linie va contine N valori 0 sau 1 separate prin câte un spatiu, reprezentând elementele vectorului R, iar a treia linie va contine M valori 0 sau 1 separate prin câte un spatiu, reprezentând elementele vectorului C.
h2. Date de iesire
...
Fisierul de iesire matrice.out va contine o singura linie pe care vor fi scrise doua numere naturale separate printr-un singur spatiu Zmax Nsol, reprezentând in ordine numarul maxim de elemente egale cu 0 intr-un dreptunghi a carui arie este exact A, precum si numarul de dreptunghiuri pentru care se obtine acest numar maxim.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N,M ≤ 30 000$
* $1 ≤ A ≤ 5 000 000$
* Pentru $40%$ din teste $N,M ≤ 300$
* Prin $x xor y$ se intelege operatia sau exclusiv, mai exact:
table. |_. x xor y | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
h2. Exemplu
table(example). |_. matrice.in |_. matrice.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 4 4
0 1
1 0 0 1
| 2 5
|
h3. Explicatie
...
Matricea B:
table. | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
Numarul maxim de valori 0 dintr-un dreptunghi de arie 4 este 2.
Cele 5 dreptunghiuri de arie 4 cu numar maxim de 0 sunt:
* (1,1)(1,4)
* (2,1)(2,4)
* (1,1)(2,2)
* (1,2)(2,3)
* (1,3)(2,4)
== include(page="template/taskfooter" task_id="matrice") ==
