C. Хамгийн том спираль

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

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

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

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

Нэгж квадрат бүхий нүднүүдтэй $k × k$ хэмжээтэй квадрат байна гэж үзье. $k ≥ 3$ бөгөөд сондгой тоо байна гэдгийг анхаараарай. Бид дараах дарааллаар зүүн дээд нүднээс эхлэн квадратыг будна: эхлээд баруун тийшээ будаад, дараа нь доошоо, тэгээд зүүн тийшээ, дээшээ, дахиад баруун тийшээ гэх мэтчилэн будна. Бид дараах хоёр тохиолдлын аль нэг тохиолдолд чигээрээ будахаа болих ёстой: квадратын хүрээнд хүрсэн, эсвэл одоо будаж байгаа квадратын дараагийн квадратын дараагийн квадрат аль хэдийнээ будагдчихсан бол чигээрээ будахаа зогсооно. Харин цааш аль ч чиглэлд будаж чадахгүй болсон бол будалтаа дуусгана. Дараах зурагт будагдсан квадратуудаас спираль үүсэж байгааг харуулсан байна.

Зурагт $k = 3, 5, 7, 9$ үеийн спиралийн жишээг харуулсан байна.

Танд нүд бүр нь тоо агуулсан $n × m$ хэмжээтэй хүснэгт байна. Хүснэгтийн нүднүүдээс үүссэн бүх боломжит спиралиудыг авч үзье. Энэ нь хүснэгтийн хүрээнээс хэтрэхгүйгээр дурын хэмжээтэй бүх спиралийг авч үзнэ гэсэн үг. Спиралийг бүрдүүлж буй нүднүүд дэх тоонуудын нийлбэрийг олцгооё. Та бүх спиралийн эдгээр утгууд дундаас хамгийн ихийг нь олох ёстой.

Оролт

Эхний мөрөнд хүснэгтийн хэмжээ болох $n$, $m$ ($3 ≤ n, m ≤ 500$) тоонууд байна.

Дараагийн $n$ ширхэг мөр бүрт зайгаар тусгаарлагдсан $m$ ширхэг тоонууд байна: $i$-р мөрийн $j$-р тоо нь $a_{ij}$ ($ - 1000 ≤ a_{ij} ≤ 1000$) нь $i$-р мөрийн $j$-р нүдэнд бичигдсэн тоо байна.

Гаралт

Нэг тоо хэвлэнэ. Энэ нь бүх спиралиуд дундаас нүднүүд дээрх тоонуудын нийлбэр нь хамгийн байх тоо юм.

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

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

Оролт
6 5
0 0 0 0 0
1 1 1 1 1
0 0 0 0 1
1 1 1 0 1
1 0 0 0 1
1 1 1 1 1
Гаралт
17
Оролт
3 3
1 1 1
1 0 0
1 1 1
Гаралт
6
Оролт
6 6
-3 2 0 1 5 -1
4 -1 2 -3 0 1
-5 1 2 4 1 -2
0 -2 1 3 -1 2
3 1 4 -3 -2 0
-1 2 -1 3 1 2
Гаралт
13

Тэмдэглэл

Эхний жишээнд хамгийн их нийлбэртэй спираль нь хүснэгтийн бүх $1$-үүдээс бүрдсэн спираль байна.

Хоёр дахь жишээнд зөвхөн зургаан $1$-ээс бүрдсэн спираль байна.

Сэтгэгдлүүдийг ачааллаж байна...