| Fişierul intrare/ieşire: | rama.in, rama.out | Sursă | Algoritmiada 2013, Runda 4 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Ionescu Vlad •vladii |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Rama
Marian, mergand linistit pe strada, a gasit o bancnota de 100 RON pe care era scrisa o matrice binara. Pentru a putea cumpara ceva cu respectiva bancnota, Marian trebuie sa gaseasca dreptunghiul de arie maxima continut in intregime in matrice, care are pe laturi numai elemente egale cu 1 (indiferent ce ar contine strict in interior). Marian nu stie, insa va roaga pe voi sa-l ajutati!
Date de intrare
Fişierul de intrare rama.in contine pe prima linie doua numere naturale N si M, separate printr-un spatiu, reprezentand numarul de linii, respectiv numarul de coloane ale matricei binare. Pe urmatoarele N linii se gasesc cate M caractere egale cu 1 sau 0, reprezentand matricea binara gasita de Marian.
Date de ieşire
În fişierul de ieşire rama.out trebuie sa afisati pe prima linie un singur numar natural: aria maxima a unui dreptunghi care are pe laturi numai elemente egale cu 1.
Restricţii si precizari
- 2 ≤ N ≤ 700
- 2 ≤ M ≤ 700
- O matrice binara este o matrice care contine numai elemente de 1 si 0.
- Dreptunghiul format dintr-un singur element de 1 se considera valid.
Exemplu
| rama.in | rama.out |
|---|---|
| 5 5 10101 10111 10101 10111 01111 | 12 |
Explicaţie
Dreptunghiul de arie maxima are coltul stanga-sus in pozitia (2, 3), iar coltul dreapta-jos in pozitia (5, 5). Existau si alte posibilitati, dar de arie mai mica: (1, 1) -> (1, 4) sau (4, 3) -> (5, 4).
