Se consideră o matrice dreptunghiulară A
cu m
linii şi n
coloane cu valori 0
sau 1
, liniile şi coloanele fiind numerotate de la 1
la m
, respectiv de la 1
la n
. Numim dreptunghi de colţuri (x1, y1) (x2,y2)
cu x1 < x2
şi y1 < y2
mulţimea elementelor A[i][j]
cu x1 ≤ i ≤ x2
si y1 ≤ j ≤ y2
. Numim perimetru al dreptunghiului de colţuri (x1, y1) (x2, y2)
mulţimea elementelor A[i][j]
pentru care (i = x1
şi y1 ≤ j ≤ y2
) sau (i = x2
şi y1 ≤ j ≤ y2
) sau (j = y1
şi x1 ≤ i ≤ x2
) sau (j = y2
şi x1 ≤ i ≤ x2
).
Cerința
Determinaţi diferenţa maximă dintre numărul de elemente egale cu 1
şi numărul de elemente egale cu 0
aflate pe perimetrul aceluiaşi dreptunghi, precum şi numărul de dreptunghiuri pentru care se obţine această diferenţă.
Date de intrare
Fișierul de intrare peri.in
conține pe prima linie numerele m
şi n
, separate printr-un singur spaţiu. Pe următoarele m
linii este dată matricea A
, numerele de pe aceeaşi linie fiind separate de câte un spaţiu.
Date de ieșire
Fișierul de ieșire peri.out
va conţine o singură linie pe care se află două numere întregi separate printr-un spaţiu. Primul număr este diferenţa maximă dintre numărul de elemente 1
şi numărul de elemente 0
de pe perimetrul unui dreptunghi. Al doilea întreg este numărul de dreptunghiuri pentru care diferenţa dintre numărul de elemente 1
şi numărul de elemente 0
de pe perimetru este maximă.
Restricții și precizări
1 ≤ m, n ≤ 250
- Prin diferenţă nu se înţelege diferenţă în valoare absolută!
Exemplu:
peri.in
4 5 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 0 1
peri.out
4 2