Fişierul intrare/ieşire:rama.in, rama.outSursăAlgoritmiada 2013, Runda 4
AutorCosmin Silvestru NegruseriAdăugată devladiiIonescu Vlad vladii
Timp execuţie pe test0.6 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inrama.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content