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:

  1. Hình chữ nhật đó chỉ gồm các số 1;
  2. Các cạnh của hình chữ nhật song song với các cạnh của bảng;
  3. 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

Không có ý kiến tại thời điểm này.