Hình chữ nhật có chu vi lớn nhất (Hard)

Xem PDF

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

Cho một bảng có kích thước \(N \times M\) (\(N\) hàng và \(M\) cột) gồm các ô vuông, mỗi ô vuông mang giá trị là \(0\) hoặc \(1\). Tìm hình chữ nhật con có chu vi lớn nhất trong bảng đã cho, biết rằng các ô vuông của hình chữ nhật này chỉ chứa toàn giá trị \(0\) và in ra giá trị đó.

Input

  • Dòng thứ nhất chứa hai số nguyên \(N, M\).
  • \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(M\) kí tự \(0\) hoặc \(1\).

Output

  • In ra một số duy nhất là chu vi lớn nhất tìm được.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(N, M \leq 25\).
  • Subtask \(2\) (\(20\%\) số điểm): \(N, M \leq 10^2\).
  • Subtask \(3\) (\(30\%\) số điểm): \(N, M \leq 5.10^2\).
  • Subtask \(4\) (\(30\%\) số điểm): \(N, M \leq 3.10^3\).

Example

Test 1

Input
2 2
00
10
Output
6
Note

Ở ví dụ \(1\), ta tìm được hình chữ nhật có kích thước \(2\text{ x }1\) có chu vi lớn nhất là \(2 * (1+2)=6\). Vậy nên đáp án là \(6\)

Test 2

Input
2 2
00
00
Output
8
Note

Ở ví dụ \(2\), hình chữ nhật đã cho đồng thời là hình chữ nhật có chu vi lớn nhất thỏa mãn yêu cầu bài toán. Do đó chu vi cần tìm là :\(2 * (2+2)=8\)


Bình luận