Editing 2665 - Dreptunghi1

== Cerinta ==

Dată fiind o matrice dreptunghiulară cu elemente 0 şi 1, care este aria maximă a unui dreptunghi format numai din elemente egale cu 1?

== Date de intrare ==

Pe prima linie a fişierului dreptunghi1.txt se vor găsi trei numere: numărul de linii, m, al matricei, numărul de coloane, n, precum şi numărul z al elementelor 0 din matrice. Pe următoarele z linii vom avea cate o pereche de numere lin şi col, separate printr-un spaţiu, cu semnificaţia că elementul de la linia lin şi coloana col este 0. Restul elementelor matricei sunt considerate 1. Este posibil ca anumite perechi lin şi col să se repete.

== Date de iesire ==

Fişierul dreptunghi1.txt va conţine un singur număr, aria celui mai mare dreptunghi plin numai cu 1.

== Restrictii si precizari ==

*1 ≤ m, n, z ≤ 10.000;
*Perechile lin şi col sunt coordonate corecte în matrice, nu neapărat unice.

== Punctaje partiale ==

*Pentru 20% din teste: 1 ≤ m, n ≤ 30;
*Pentru 40% din teste: 1 ≤ m, n ≤ 100.

== Exemplul 1 ==
;Intrare
:6 6 3
:4 1
:4 5
:3 3
;Iesire
;Datele introduse corespund restrictiilor impuse
:12

== Exemplul 2 ==
;Intrare
:1 2
:0 0
:-1 -2 -3
;Iesire
;Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def arie_maxima_dreptunghi(matrix):
    def arie_histograma_maxima(inaltimi):
        stack = []
        max_arie = 0
        i = 0

        while i < len(inaltimi):
            if not stack or inaltimi[i] >= inaltimi[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                top = stack.pop()
                latime = i if not stack else i - stack[-1] - 1
                max_arie = max(max_arie, inaltimi[top] * latime)

        while stack:
            top = stack.pop()
            latime = i if not stack else i - stack[-1] - 1
            max_arie = max(max_arie, inaltimi[top] * latime)

        return max_arie

    max_arie = 0
    histograma_rand = [0] * len(matrix[0])

    for rand in matrix:
        for i in range(len(rand)):
            if rand[i] == 0:
                histograma_rand[i] = 0
            else:
                histograma_rand[i] += 1

        max_arie = max(max_arie, arie_histograma_maxima(histograma_rand))

    return max_arie

def main():
    with open("dreptunghi1.txt", "r") as fisier:
        m, n, z = map(int, fisier.readline().split())
        matrice = [[1] * n for _ in range(m)]

        for _ in range(z):
            linie, coloana = map(int, fisier.readline().split())
            matrice[linie - 1][coloana - 1] = 0

    rezultat = arie_maxima_dreptunghi(matrice)

    with open("dreptunghi1.txt", "w") as fisier_out:
        fisier_out.write(str(rezultat))

if __name__ == "__main__":
    main()

</syntaxhighlight>

== Explicatie ==

Matricea este:
;111111
;111111
:110111
:011101
:111111
:111111
Cel mai mare dreptunghi are arie 12.