Fişierul intrare/ieşire:logs.in, logs.outSursăCEOI 2009
AutorCosmin Silvestru NegruseriAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Logs

Fiind dată o matrice binară de dimensiuni N x M, să se determine aria celui mai mare dreptunghi, care conţine numai valoarea 1, cunoscând că puteţi permuta coloanele matricei.

Date de intrare

Prima linie a fişierului de intrare logs.in conţine două numere întregi separate printr-un spaţiu: N şi M. Următoarele N linii vor conţine câte M caractere de 0 sau 1, descriind matricea.

Date de ieşire

Singura linie a fişierului de intrare logs.out va conţine aria celui mai mare dreptunghi.

Restricţii şi precizări

  • 1 ≤ N ≤ 15.000
  • 1 ≤ M ≤ 1.500
  • 30% din teste vor avea N, M ≤ 1.024.
  • Se recomandă parsarea fişierului de intrare folosind funcţiile fgets pentru C/C++ respectiv readln() şi settextbuf pentru Pascal.

Exemplu

logs.inlogs.out
10 6
001010
111110
011110
111110
011110
111111
110111
110111
000101
010101
21

Explicaţie

Prin permutarea coloanelor astfel încât coloanele 2, 4 şi 5 devin adiacente se obţine un dreptunghi având aria 21 (liniile 2-8 şi coloanele 2, 4, 5).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content