Hình chữ nhật 0 1

Xem dưới dạng PDF

Gửi bài giải

Điểm: 20
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
Kiểu bài tập

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 thỏa 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ể.

Dữ liệu vào:

  • Dòng 1: Ghi hai số \(M, N\).
  • Dòng thứ \(i\) trong \(M\) dòng tiếp theo: Ghi \(N\) số mà số thứ \(j\) là số ghi trên ô \((i, j)\) của bảng.

Dữ liệu ra:

  • Gồm \(1\) dòng duy nhất ghi diện tích của hình chữ nhật tìm được.

Input 1

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 1

49

Nhận xét

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