B. Хамгийн их дэд матриц 2

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэг болон тэгээс бүрдсэн $n × m$ хэмжээтэй матриц өгөгджээ. Мөрүүдийн байрыг солих үйлдэл зөвшөөрөгдсөн. Тэгвэл уг үйлдлээр бий болгож болох зөвхөн нэгүүдээс бүрдсэн хамгийн их талбайтай дэд матрицын талбайг олно уу?

$a$ матрицын мөрийг дээрээс доошоо $1$-с $n$ хүртэл, багануудыг зүүнээс баруун тийш $1$-с $m$ хүртэл дугаарлагдсан гэж үзье. Матрицын $i$-р мөр болон $j$-р баганы огтлолцлын нүдийг $(i, j)$ илэрхийлнэ. Өөрөөр хэлбэл, $a$ матрицийн дэд матриц бол $d, u, l, r$ $(1 ≤ d ≤ u ≤ n; 1 ≤ l ≤ r ≤ m)$ дөрвөн бүхэл тооны групп юм. Бид дэд матриц $(i, j)$ $(d ≤ i ≤ u; l ≤ j ≤ r)$ нүдийг агуулсан байна гэж үзье. Дэд матрицын талбай нь агуулсан нүднүүдийнх нь тоо юм.

Оролт

Эхний мөр нь $n$, $m$ $(1 ≤ n, m ≤ 5000)$ хоёр бүхэл тоо агуулна. Дараагийн $n$ мөр бүр нь $a$ матрицын $m$ тэмдэгтүүдийг агуулна. $a$ матриц нь зөвхөн "$0$" болон "$1$"-н тэмдэгт агуулна. Матрицийн элементийн мөрүүдэд ямар ч зай байхгүй болохыг анхаарна уу.

Гаралт

Гарган авж болох дэд матрицын боломжит хамгийн их талбай. Хэрвээ нэгүүдээс тогтсон матриц гарган авах боломжгүй бол 0-г хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
1 1
1
Гаралт
1
Оролт
2 2
10
11
Гаралт
2
Оролт
4 3
100
011
000
101
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...