E. Хоёр тойрог

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

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

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

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

Бидэнд бүхэл тоонуудаар бөглөсөн $n × m$ хүснэгт өгөгдсөн гэж үзье. Бид $i$-р мөр $j$-р багана дахь нүдийг ($i, j$) гэж тэмдэглэнэ. Иймээс ($1, 1$) нь хүснэгтийн зүүн дээд, ($n, m$) нь баруун доод нүд болно. Бид ($i_0, j_0$) нүдэнд төвтэй r радиустай тойргийг нөхцөлийг хангах ($i, j$) нүднүүдийн олонлог гэж үзнэ. Бид зөвхөн хүснэгтийн хязгаараас давж гардаггүй буюу $r + 1 ≤ i_0 ≤ n - r$ болон $r + 1 ≤ j_0 ≤ m - r$ байх тойргуудыг авч үзэх болно.

(4, 5) нүдэнд төвтэй 3 радиустай тойрог

Өгөгдсөн $r$ радиустай эдгээр тойргуудад багтсан нүднүүдийн нийлбэр нь хамгийн их байх хоёр үл огтолцох тойргуудыг ол. Хоёр тойрог хоёуланд нь зэрэг харъяалагддаг нүд байгаа тохиолдолд огтолцоно гэж үзнэ. Нийлбэр нь хамгийн их байх хоёр тойрог сонгох зам нэгээс олон байж болно, иймд бид мөн ийм хосуудын тоог сонирхож байгаа болно. Сонгосон 2 тойрог нь эрэмбэгүй гэж үз. Жишээлбэл $2$ радиустай ($3, 4$) болон ($7, 7$) дээр төвтэй тойргуудын хос нь ($7, 7$) болон ($3, 4$) дээр төвтэй тойргуудтай адил хос юм.

Оролт

Эхний мөр $n$, $m$ ба $r$ ($2 ≤ n, m ≤ 500$, $r ≥ 0$) гэсэн 3 ширхэг бүхэл тоо агуулна. Дараагийн $n$ мөр тус бүр хүснэгтийн элементүүд болох $1-1000$ хоорондох $m$ ширхэг бүхэл тоо агуулна. Хүснэгтийн мөрнүүд нь дээрээс доош, мөрийн элементүүд нь зүүнээс баруун тийш бичигдсэн болно. Оролтонд дор хаяж нэг $r$ радиутай, хүснэгтийн хязгаарыг давахгүй тойрог байна.

Гаралт

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

Орчуулсан: Энхдүүрэн, zoloogg

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

Оролт
2 2 0
1 2
2 4
Гаралт
6 2
Оролт
5 6 1
4 2 1 3 2 6
2 3 2 4 7 2
5 2 2 1 1 3
1 4 3 3 6 4
5 1 4 2 3 2
Гаралт
34 3
Оролт
3 3 1
1 2 3
4 5 6
7 8 9
Гаралт
0 0
Сэтгэгдлүүдийг ачааллаж байна...