Fişierul intrare/ieşire:	submat.in, submat.out	Sursă	ONI 2008, clasa a 8-a
Autor	Stelian Ciurea	Adăugată de	Radu Zernoveanu •raduzer
Timp execuţie pe test	0.1 sec	Limită de memorie	4736 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Submat

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

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.

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.

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.

Date de iesire

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

Restrictii

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

Exemplu

Explicatie

...

Cum se trimit solutii?