HÌNH CHỮ NHẬT 0 1
Gửi bài giải
Điểm:
20
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Tác giả:
Kiểu bài tập
Ngôn ngữ cho phép
C++, Python
Cho một bảng kích thước M × N, được chia thành lưới ô vuông đơn vị gồm M dòng và N cột (1 ≤ M, N ≤ 1000).
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 đá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 thỏa mãn các điều kiện sau:
- Hình chữ nhật đó chỉ gồm các số 1;
- Các cạnh của hình chữ nhật song song với các cạnh của bảng;
- Diện tích hình chữ nhật là lớn nhất có thể.
INPUT
- Dòng đầu tiên chứa hai số nguyên M, N;
- M dòng tiếp theo, dòng thứ i chứa N số, số thứ j là số ghi trên ô (i, j) của bảng.
OUTPUT
Ghi ra một số nguyên duy nhất là diện tích lớn nhất của hình chữ nhật tìm được.
Ví dụ
Sample 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
Sample Output
49
Nhận xét