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

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 256M 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

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

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 (2)

Tải bình luận...