Problem
https://vn.spoj.com/problems/QBRECT
https://oj.vnoi.info/problem/QBRECT
Cho một bảng kích thước MxN
, được chia thành lưới ô vuông đơn vị M
dòng N
cột (1 <= M, N <= 1,000
)
Trên các ô của bảng ghi số 0
hoặc 1
. Các dòng của bảng được đánh số 1, 2... M
theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số 1, 2..., N
theo thứ tự từ trái qua phải
Yêu cầu:
Hãy tìm một hình chữ nhật gồm các ô của bảng thoả mãn các điều kiện sau:
- Hình chữ nhật đó chỉ gồm các số
1
- Cạnh hình chữ nhật song song với cạnh bảng
- Diện tích hình chữ nhật là lớn nhất có thể
Input
Dòng 1: Ghi hai số M
, N
M
dòng tiếp theo, dòng thứ i
ghi N
số mà số thứ j
là số ghi trên ô (i, j)
của bảng
Output
Gồm 1 dòng duy nhất ghi diện tích của hình chữ nhật tìm được
Example
Input
11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1
Output
49
Tutorial
Submission
QBRECT.cpp