== 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 {$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.
h2. Date de intrare
...
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$}, 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
* $... ≤ ... ≤ ...$
* $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{width:10%}. |_. 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{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:
* ({$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="...") ==
