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 '''dreptunghi1in.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 '''dreptunghi1out.txt''' va conţine un singur număr, aria celui mai mare dreptunghi plin numai cu 1.

== Restrictii si precizari ==

*'''1 &les; m, n, z &les; 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 ==
;dreptunghi1in.txt
:6 6 3
:4 1
:4 5
:3 3
;dreptunghi1out.txt
:Datele introduse corespund restrictiilor impuse
:12

== Exemplul 2 ==
;dreptunghi1in.txt
:1 2
:0 0
:-1 -2 -3

:Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_rezultat_corect(m, n, z, pozitii_0, aria_maxima):
    if not (1 <= m <= 10000 and 1 <= n <= 10000 and 1 <= z <= 10000):
        return False

    for lin, col in pozitii_0:
        if not (0 <= lin < m and 0 <= col < n):
            return False

    if not (0 <= aria_maxima <= m * n):
        return False

    return True

# Citire date de intrare
with open("dreptunghi1in.txt", "r") as f:
    m, n, z = map(int, f.readline().split())
    pozitii_0 = [tuple(map(int, f.readline().split())) for _ in range(z)]

# Calculare aria maxima
aria_maxima = calculeaza_aria_maxima(m, n, z, pozitii_0)

# Scriere rezultat în fișier de ieșire
with open("dreptunghi1out.txt", "w") as f_out:
    if verificare_rezultat_corect(m, n, z, pozitii_0, aria_maxima):
        f_out.write(f"{aria_maxima}\n")
    else:
        f_out.write("Datele introduse nu corespund restrictiilor impuse.\n")

</syntaxhighlight>

== Explicatie ==

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