Cho một bảng hình chũ nhật kích thước ~m \times n~, được chia thành các ô vuông đơn vị. Trên mỗi ô, người ta ghi số ~0~ hoặc số ~1~. Một hình vuông được gọi là đẹp nếu:
Hình vuông chiếm trọn một số ô của bảng.
Có các cạnh song song với hình chữ nhật ban đầu.
Các ô ở viền ngoài của hình vuông được chọn chỉ gồm toàn số ~1~.
Ví dụ: hình chữ nhật dưới đây có kích thước ~8 \times 10~, ta có thể tìm được một hình vuông kích thước ~6 \times 6~ mà viền ngoài của hình vuông đó chỉ gồm các số ~1~:
Yêu cầu: Tìm một hình vuông đẹp có diện tích lớn nhất (Diện tích của hình vuông là số ô của nó).
Dữ liệu:
Dòng đầu gồm hai số nguyên dương ~m, n\left(m \times n \leq 10^{6}\right)~
~m~ dòng tiếp theo, mỗi dòng ghi ~n~ số (chỉ gồm các số ~0,1~ cách nhau bởi dấu cách) mô tả bảng.
Kết quả:
- Ghi ra một số duy nhất là diện tích hình vuông tìm được.
Ví dụ:
Sample Input 1
4 6
0 0 0 0 0 0
0 1 1 0 1 0
0 1 1 0 1 0
0 0 0 0 0 0
Sample Output 1
4
Sample Input 2
4 6
0 0 0 0 0 0
0 0 1 1 1 0
0 1 1 0 1 0
0 0 0 0 0 0
Sample Output 2
1
Ràng buộc:
Subtask 1: Có ~50 \%~ số test có ~m, n \leq 300~;
Subtask 2: ~50\%~ số test còn lại không có ràng buộc gì thêm.
Comments