submat

Submat

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

Poveste si cerinta...

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.
 
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 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 nula ce se poate obtine printr-o rearanjare a liniilor matricei date.

h2. Date de intrare

Fisierul de intrare $submat.in$ ...

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

In fisierul de iesire $submat.out$ ...

Fisierul de iesire $submat.out$ va contine o singura linie pe care va fi scris un numar natural reprezentand numarul maxim de elemente pe care il contine o submatrice nula rezultata in urma rearanjarilor liniilor matricei $a$

h2. Restrictii

* $... ≤ ... ≤ ...$

* $2$ ≤ $n, m$ ≤ $1000$
* Pentru $60%$ din teste $n, m$ ≤ $100$.

h2. Exemplu
table(example). |_. submat.in |_. submat.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| $3 5$
  $0 0 0 1 1$
  $0 1 1 1 1$
  $0 0 0 0 1$
| $6$

|
h3. Explicatie

...

Daca rearanjam liniile astfel incat matricea rezultata sa fie urmatoarea:
$0 0 0 1 1$
$0 0 0 0 1$
$0 1 1 1 1$
atunci observam ca submatricea determinata de prima si a doua linie si de prima si a treia coloana contine $6$ valori de $0$ ( $6$ fiind numarul maxim posibil).

== include(page="template/taskfooter" task_id="submat") ==

2741