mmx

Colegiul Național “Frații Buzești”
Centrul de Pregătire pentru Performanță în Informatică
InfoCNFB - Ediția a II-a, Juniori
9 decembrie 2023

Cerință

Se dă o matrice cu $0$ și $1$. Se cunoaște că elementele $1$ de pe fiecare linie sunt unul lângă altul. Să se determine o submatrice plină de $1$, 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 $n$ și $m$ reprezentând dimensiunile matricei date ($n$ reprezintă numărul de linii iar $m$ numărul de coloane).

Pe următoarele $n$ linii se află câte două numere separate prin spațiu. Valorile de pe a $i$-a dintre aceste $n$ linii reprezentând poziția primei și a ultimei coloane unde se află elemente de $1$ pe linia $i$ 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

• $1 \leq n, m \leq 100 \ 000$;
• Se garantează că numerele de pe liniile $2, \dots, n+1$ din fișierul de intrare sunt cuprinse între $1$ și $m$;
• Pentru $21$ de puncte avem $n, m \leq 20$;
• Pentru alte $35$ de puncte avem $n, 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