== include(page="template/taskheader" task_id="matrice") ==

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).

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 {$B{~i,j~} = R{~i~} xor C{~j~}$}, unde $R$ si $C$ sunt vectori binari de lungime {$N$}, respectiv {$M$}. Numim dreptunghi de colturi ({$x{~1~},y{~1~}$}) ({$x{~2~},y{~2~}$}) cu {$x{~1~} ≤ x{~2~}$} si {$y{~1~} ≤ y{~2~}$}, multimea elementelor {$B{~i,j~}$} cu {$x{~1~} ≤ i ≤ x{~2~}$} si {$y{~1~} ≤ j ≤ y{~2~}$}. Aria unui astfel de dreptunghi este {$(x{~2~}-x{~1~}+1)*(y{~2~}-y{~1~}+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.

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.

Fisierul de intrare $matrice.in$ contine pe prima linie numerele naturale {$N$}, {$M$}, {$A$} separate prin cate un spatiu. A doua linie va contine $N$ valori $0$ sau $1$ separate prin cate un spatiu, reprezentand elementele vectorului {$R$}, iar a treia linie va contine $M$ valori $0$ sau $1$ separate prin cate un spatiu, reprezentand 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.

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$}, reprezentand 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

* 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 |

table{width:10%}. |_. x xor y | {$0 $} | {$1$} |
| {$0 $} | {$0 $} | {$1$} |
| {$1$} | {$1$} | 0  |

h2. Exemplu

h3. Explicatie

Matricea B:

Matricea {$B$}:

table. | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |

table{width:10%}. | {$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:

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)

* ({$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") ==

== SmfTopic(topic_id="...") ==

1833