Se considera o matrice $A$ cu urmatoarele proprietati:
- contine $n$ linii si $m$ coloane;
- contine doar valorile $0$ si $1$;
- pe fiecare linie valorile sunt plasate in ordine crescatoare.
* contine $n$ linii si $m$ coloane;
* contine doar valorile $0$ si $1$;
* pe fiecare linie valorile sunt plasate in ordine crescatoare.
Definim o submatrice determinatade perechea de linii $L1$ si $L2$ ($L1$ ≤ $L2$) si de percechea de coloane $C1$ si $C2$ ($C1$ ≤ $C2$) ca fiind totalitatea elementelor matricei $A{~i,j~}$ pentru care $L1$ ≤ $i$ ≤ $L2$ si $C1$ ≤ $i$ ≤ $C2$.
Definim o submatrice determinata de perechea de linii $L{~1~}$ si $L{~2~}$ ( $L{~1~} ≤ L{~2~}$ ) si de percechea de coloane $C{~1~}$ si $C{~2~}$ ( $C{~1~} ≤ C{~2~}$ ) ca fiind totalitatea elementelor matricei $A{~i,j~}$ pentru care $L{~1~}$ ≤ $i$ ≤ $L{~2~}$ si $C{~1~}$ ≤ $j$ ≤ $C{~2~}$.
Daca toate elementele unei submatrici sunt egale cu $0$, atunci submatricea se numeste nula.
Asupra matricei $A$ putem efectua una sau mai multe operatii de interschimbari de linii. Prin astfel de interschimbari liniile matricei pot fi rearanjate astfel incatmatricea $A$ sa contina cel putin o submatrice nula cu numar maxim de elemente.
Asupra matricei $A$ putem efectua una sau mai multe operatii de interschimbari de linii. Prin astfel de interschimbari liniile matricei pot fi rearanjate astfel incat matricea $A$ sa contina cel putin o submatrice nula cu numar maxim de elemente.
h2. Cerinta
Fiind data o astfel de matrice se cere sa se determine numarul maxim de zerouri dintr-o submatrice nule ce se poate obtine printr-o rearanjare a liniilor matricei date.
Fiind data o astfel de matrice se cere sa se determine numarul maxim de zerouri dintr-o submatrice nula ce se poate obtine printr-o rearanjare a liniilor matricei date.
h2. Date de intrare
Fisierul de intrare $submat.in$ contine pe prima linie doua numere naturale $n m$, separate printr-un spatiu, reprezentand numarul de linii, respectiv numarul de coloane ale matricei $A$. Pe urmatoarele $n$ linii ale fisieruluisunt descrise cele $n$ linii ale matricei $A$; pe fiecare linie din cele $n$ vor fi scrise cate $m$ valori de $0$ sau $1$, separate prin spatii, reprezentant in ordine elementele liniei respective.
Fisierul de intrare $submat.in$ contine pe prima linie doua numere naturale $n m$, separate printr-un spatiu, reprezentand numarul de linii, respectiv numarul de coloane ale matricei $A$. Pe urmatoarele $n$ linii ale fisierului sunt descrise cele $n$ linii ale matricei $A$; pe fiecare linie din cele $n$ vor fi scrise cate $m$ valori de $0$ sau $1$, separate prin spatii, reprezentant in ordine elementele liniei respective.
h2. Date de iesire
