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 și . Se cunoaște că elementele de pe fiecare linie sunt unul lângă altul. Să se determine o submatrice plină de , 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 și reprezentând dimensiunile matricei date ( reprezintă numărul de linii iar numărul de coloane).
Pe următoarele linii se află câte două numere separate prin spațiu. Valorile de pe a -a dintre aceste linii reprezentând poziția primei și a ultimei coloane unde se află elemente de pe linia 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
- ;
- Se garantează că numerele de pe liniile din fișierul de intrare sunt cuprinse între și ;
- Pentru de puncte avem ;
- Pentru alte de puncte avem ;
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