Thời trang caro

Xem PDF



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: 1600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

𝔻𝔸𝔹𝔸 là một nhà thiết kế thời trang tài năng và cô vừa mua được một mảnh vải siêu to khổng lồ khi đi thăm phố Cổ. Tuy nhiên, trước khi có thể sử dụng mảnh vải này để may vá quần áo, 𝔻𝔸𝔹𝔸 cần cắt nó thành một mảnh vải con hình chữ nhật sao cho không có hai ô chung cạnh nào có cùng màu. Mảnh vải ban đầu có kích thước \(N\) hàng và \(M\) cột, tạo thành \(N \times M\) ô với mỗi ô có thể là màu đen hoặc trắng. Bạn hãy giúp 𝔻𝔸𝔹𝔸 tính toán xem cô có thể cắt ra một mảnh vải con lớn nhất có bao nhiêu ô để tạo ra những thiết kế thời trang đẹp mắt nhé!

Input

  • Dòng đầu tiên bao gồm hai số nguyên dương \(N\), \(M\).
  • \(N\) dòng tiếp theo, dòng thứ \(i\) bao gồm \(M\) số nguyên \(a_{i1}, a_{i2}, \dots, a_{iM}\). Trong đó \(a_{ij} = 0\) có nghĩa là ô ở hàng \(i\) cột \(j\) của hình ban đầu là có màu trắng, \(a_{ij} = 1\) nghĩa là ô đó có màu đen

Output

  • Gồm 1 số nguyên duy nhất là diện tích của hình chữ nhật mà mình cần tìm.

Example

Example

Input
4 5
0 0 0 0 0
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0
Output
6

Scoring

  • \(30\%\) số điểm có \(1 \le N, M \le 10\)
  • \(30\%\) số điểm có \(N = 1\); \(M \le 10^5\)
  • \(40\%\) số điểm có \(1 \le N, M \le 10^3\)

Bình luận

Mới nhất
Tải bình luận...

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