mmx

Time limit: 0.2s Memory limit: 64MB Input: mmx.in Output: mmx.out

Cerință

Se dă o matrice cu 00 și 11. Se cunoaște că elementele 11 de pe fiecare linie sunt unul lângă altul. Să se determine o submatrice plină de 11, cu linia de sus pe prima linie a matricei, și cu aria maximă.

Date de intrare

Fișierul mmx.in conține pe prima linie două numere nn și mm reprezentând dimensiunile matricei date (nn reprezintă numărul de linii iar mm numărul de coloane).

Pe următoarele nn linii se află câte două numere separate prin spațiu. Valorile de pe a ii-a dintre aceste nn linii reprezentând poziția primei și a ultimei coloane unde se află elemente de 11 pe linia ii a matricei.

Date de ieșire

Fișierul mmx.out conține pe prima linie un număr natural reprezentând aria determinată.

Restricții și precizări

  • 1n,m100 0001 \leq n, m \leq 100 \ 000;
  • Se garantează că numerele de pe liniile 2,,n+12, \dots, n+1 din fișierul de intrare sunt cuprinse între 11 și mm;
  • Pentru 2121 de puncte avem n,m20n, m \leq 20;
  • Pentru alte 3535 de puncte avem n,m100n, m \leq 100;

Exemplu

mmx.in

4 7
2 6
4 7
1 5
5 5

mmx.out

6

Explicație

0 1 1 1 1 1 0
0 0 0 1 1 1 1
1 1 1 1 1 0 0
0 0 0 0 1 0 0

Log in or sign up to be able to send submissions!