Hình chữ nhật 0 1

Xem PDF

Điểm: 1700 (p) Thời gian: 0.2s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một bảng kích thước \(M \times N\), được chia thành lưới ô vuông đơn vị \(M\) dòng \(N\) cột (\(1 \le M, N \le 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ủ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:

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

Test 1

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

Bình luận

Không có bình luận nào.