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