E. Ромбо

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

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

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

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

Таньд $n × m$ хэмжээтэй ширээ өгөгдөв. $i$ дэх мөр ба $j$ дэх баганын огтлолцол дээр сөрөг биш $a_{i, j}$ бүхэл тоо оршино.Мөн таньд сөрөг биш $k$ бүхэл тоо өгөгдөв.

Таны даалгавар бол доорхи нөхцөлийг хангах $(a, b)$ бүхэл хосуудыг олох явдал юм. Үүнд:

  • $k ≤ a ≤ n - k + 1$;
  • $k ≤ b ≤ m - k + 1$;
  • Доорхи функцын хамгийн их утгыг $mval$ гэж тэмдэглэх бөгөөд шаардлага хангах хос нь $f(a, b) = mval$ нөхцөлийг заавал хангах ёстой. $f(x, y) = \sum\limits_{i=1}^n\sum\limits_{j=1}^m a_{i,j} \cdot max(0, k-|i-x| - |j-y|)$

    (функц доторх $x$ ба $y$ бүхэл тоонууд нь $k ≤ x ≤ n - k + 1$ ба $k ≤ y ≤ m - k + 1$ тэнцэтгэл бишийг хангана.)

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан $n$, $m$, $k$ бүхэл тоонууд өгөгдөнө. ($1 ≤ n, m ≤ 1000$, $1 ≤ k ≤ \lfloor\frac{min(n,m)+1}{2}\rfloor$) Дараачийн $n$ мөрөнд тус бүр $m$ ширхэг бүхэл тоо өгөгдөх ба $i$ дэх мөрийн $j$ дэх тоог $a_{i, j}$ гэж үзнэ. ($0 ≤ a_{i, j} ≤ 10^{6}$). Мөр бүрт орших тоонууд зайгаар тусгаарлагдсан байна.

Гаралт

Шаардлагатай байгаа $a$ ба $b$ хосуудыг хэвлэнэ. Тоонууд нь зайгаар тусгаарлагдсан байна. Хэрэв нэгээс олон хариулт байгаа бол та аль ч хариултыг хэвлэсэн болно.

Орчуулсан: Баатархүү

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

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