Codeforces Round #804 (Div. 2)
22:57:51 |
Educational Codeforces Round 131 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #805 (Div. 3)
6 өдрийн дараа |
Codeforces Round #806 (Div. 4)
8 өдрийн дараа |
C. Гаргари ба тэмээнүүд
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Гаргари түүний найз Кайсаг ѳмнѳх бодлогон дахь тоглоомонд хожсонд нь хардаж атаархаж байлаа. Тэрээр ѳѳрийгѳѳ суут ухаантан гэдгийг батлахыг хүсч байв.
Түүнд $n × n$ шатрын хѳлѳг байгаа. Нүд бүрт нь тоо бичсэн байв. Гаргари хѳлѳг дээр хоёр тэмээг хоюуланд нь идэгдэх нүд байхгүй байхаар байрлуулахыг хүсч байна. Тэмээнд идэгдэх нүднүүд дээрх тоонуудын нийлбэртэй тэнцүү хэмжээний долларыг Гаргари авна. Хэрхэн байрлуулбал хамгийн их доллар авахыг Гаргарид хэлнэ үү.
Тэмээнд идүүлэх нүд гэж тэмээтэй нэг диагональд оршиж байгаа нүднүүдийг хэлнэ (тэмээний байрлаж байгаа нүдийг түүнд идэгдэх нүд гэж үзнэ).
Оролт
Эхний мѳр $n$ $(2 ≤ n ≤ 2000)$ бүхэл тоог агуулна. Дараагийн $n$ мѳр бүр хѳлгийн нүднүүд дэх тоог илэрхийлэх $n$ ширхэг бүхэл тоо $a_{ij}$ $(0 ≤ a_{ij} ≤ 10^{9})$ агуулна.
Гаралт
Эхний мѳрѳнд Гаргарийн олж болох хамгийн их долларын хэмжээг хэвлэнэ. Дараагийн мѳрѳнд уг долларыг олохын тулд хэрхэн байрлуулахыг заах дѳрвѳн бүхэл тоо $x_{1}, y_{1}, x_{2}, y_{2}$ $(1 ≤ x_{1}, y_{1}, x_{2}, y_{2} ≤ n)$ хэвлэ, энд $x_{i}$, $y_{i}$ нь $i$-р тэмээний байрлах мѳр баганын дугаар. Мѳрийг дээрээс доош, баганыг зүүнээс баруун тийш $1$-ээс $n$ хүртэл дугаарлана.
Хэд хэдэн хариутай бол аль нэгийг нь хэвлэ.
Орчуулсан: Sugardorj
Жишээ тэстүүд
Оролт
4 1 1 1 1 2 1 1 0 1 1 1 0 1 0 0 1
Гаралт
12 2 2 3 2