Se consideră o matrice A cu următoarele proprietăţi:

conţine n linii şi m coloane;
conţine doar valorile 0 şi 1;
pe fiecare linie valorile sunt plasate în ordine crescătoare.

Definim o submatrice determinată de perechea de linii L1 şi L2 (L1 ≤ L2) şi de perechea de coloane C1 şi C2 (C1 ≤ C2) ca fiind totalitatea elementelor matricei A[i,j] pentru care L1 ≤ i ≤ L2 şi C1 ≤ j ≤ C2.
Dacă toate elementele unei submatrice sunt egale cu 0, atunci submatricea se numeşte nulă.
Asupra matricei A putem efectua una sau mai multe operaţii de interschimbări de linii. Prin astfel de interschimbări liniile matricei pot fi rearanjate astfel încât matricea A să conţină cel puţin o submatrice nulă cu număr maxim de elemente.

Cerința

Fiind dată o astfel de matrice se cere să se determine numărul maxim de zerouri dintr-o submatrice nulă ce se poate obţine printr-o rearanjare a liniilor matricei date.

Date de intrare

Fișierul de intrare submat1.in conţine pe prima linie două numere naturale n m, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale matricei A. Pe următoarele n linii ale fişierului sunt descrise cele n linii ale matricei A; pe fiecare linie din cele n vor fi scrise câte m valori din mulţimea {0, 1}, separate prin spaţii, reprezentând în ordine elementele liniei respective.

Date de ieșire

Fișierul de ieșire submat1.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de elemente pe care îl conţine o submatrice nulă rezultată în urma rearanjărilor liniilor matricei A.

Restricții și precizări

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

Exemplu

submat1.in

submat1.out

Explicație

Dacă rearanjăm liniile astfel încât matricea rezultată să fie următoarea:
0 0 0 1 1
0 0 0 0 1
0 1 1 1 1
atunci se observă că submatricea determinată de prima şi a doua linie şi de prima şi a treia coloană conţine 6 valori de 0 (6 fiind numărul maxim posibil).

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema submat1:

#include <bits/stdc++.h>
using namespace std;

int a[1005], n, m;

int main()
{
    int i, j, aria, x;
    ifstream fin("submat1.in");
    ofstream fout("submat1.out");
    fin >> n >> m;
    for (i = 1; i <= n; ++i)
    {
        a[i] = 0;
        for (j = 1; j <= m; j++)
        {
            fin >> x;
            if (x == 0) a[i]++;
        }
    }
    sort(a + 1, a + n + 1, greater<int>());
    aria = 0;
    for (i = 1; i <= n; i++)
        if (aria < i * a[i]) aria = i * a[i];
    fout << aria << "\n";
    fin.close();
    fout.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2412 submat1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2412 submat1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2412 submat1