Editing 2412 - Sub Mat 1

== 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
<br>
~ Pentru 60% din teste n, m ≤ 100.
== Exemplu 1 ==
; Intrare
: submat1.in 
:3 5
:0 0 0 1 1
:0 1 1 1 1
:0 0 0 0 1
; Ieșire
: submat1.out
:6
<br>
== Exemplu 2 ==
; Intrare
: submat1.in
:4 2
:0 0 
:1 1
:0 1
:0 0
; Ieșire
:5
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#2412 - Sub Mat 1
def numar_maxim_zerouri(matrice):
    numar_linii = len(matrice)
    numar_coloane = len(matrice[0])

    matrice.sort(key=lambda linie: linie.count(0), reverse=True)

    prefixe = [linie.copy() for linie in matrice]
    for i in range(numar_linii):
        for j in range(1, numar_coloane):
            prefixe[i][j] += prefixe[i][j - 1]

    rezultat = 0

    for i in range(numar_linii):
        for j in range(i, numar_linii):
            numar_zerouri = prefixe[j][-1] if i == 0 else prefixe[j][-1] - prefixe[i - 1][-1]
            rezultat = max(rezultat, numar_zerouri * (j - i + 1))

    return rezultat

def main():
    with open("submat1.in", "r") as file_in:
        n, m = map(int, file_in.readline().split())
        matrice = [list(map(int, file_in.readline().split())) for _ in range(n)]

    rezultat = numar_maxim_zerouri(matrice)

    with open("submat1.out", "w") as file_out:
        file_out.write(str(rezultat))

if __name__ == "__main__":
    main()
</syntaxhighlight>