Rezolvare PBinfo #3389

Cerința

Se dă o matrice cu n linii și m coloane cu valori de 0 și 1. Numim dreptunghi de extrem un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă.

Date de intrare

Fișierul de intrare colturi_dr.in conține pe prima linie numărul n de linii, numărul m de coloane, iar pe următoarele linii se află cele n * m numere naturale.

Date de ieșire

Fișierul de ieșire colturi_dr.out va conține pe prima linie numerele nr, A si cnt reprezentând cele trei numere specificate în cerință.

Restricții și precizări

• 1 ≤ n, m ≤ 100
• numărul de dreptunghiuri de extrem cu vârfuri de 1 este diferit de numărul de dreptunghiuri de extrem cu vârfuri de 0.
• un dreptunghi de extrem are cel puțin două linii și două coloane

Exemplu:

colturi_dr.in

5 5
1  0  1  0  1
1  1  1  1  0
0  1  1  0  1
0  1  0  0  1
1  0  1  0  1

colturi_dr.out

11 25 9

Explicație

Sunt 9 dreptunghiuri de extrem a cărui vârfuri sunt 1, respectiv 2 ale cărui vârfuri sunt 0. Dreptunghiul de extrem de arie maximă are colțul stânga sus la (0,0) și colțul dreapta jos la (5,5).