2412 - Sub Mat 1

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 submat1IN.txt 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 submat1OUT.txt 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. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

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

Exemplul 1:

submat1IN.txt

3 5
0 0 0 1 1
0 1 1 1 1
0 0 0 0 1

submat1OUT.txt

6

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

Exemplul 2:

submat1IN.txt

1 5
0 0 0 1 1
0 1 1 1 1
0 0 0 0 1

submat1OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def verifica_restricii(n, m):
    return 2 <= n <= 1000 and 2 <= m <= 1000

def main():
    with open('submat1IN.txt', 'r') as fin:
        n, m = map(int, fin.readline().split())

    if not verifica_restricii(n, m):
        with open('submat1OUT.txt', 'w') as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        return  
    a = [0] * n
    with open('submat1IN.txt', 'r') as fin:
        next(fin)  
        for i in range(n):
            linie = list(map(int, fin.readline().split()))
            a[i] = linie.count(0)

    a.sort(reverse=True)
    aria = 0
    for i in range(n):
        if aria < (i + 1) * a[i]:
            aria = (i + 1) * a[i]

    with open('submat1OUT.txt', 'w') as fout:
        fout.write(str(aria) + '\n')

if __name__ == '__main__':
    main()