QBRECT - Hình chữ nhật 0 1

Tags: stack, dp, greedy

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:

  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

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