B. Шүршүүрийн дараалал

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

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

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

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

Дотуур байр бол олон оюутан амьдардаг болоод ч тэр үү хөгжилтэй, зугаатай мөн олон боломжуудтай бүхэл бүтэн шинэ ертөнц байдаг боловч түүнд сул талууд бас байдаг.

Дотуур байранд зөвхөн нэг шүршүүр байдаг ба олон оюутан өглөө усанд орохыг хүсдэг. Тийм учраас өглөө бүр дотуур байрны шүршүүрийн хаалганы өмнө таван хүний дараалал байдаг. Удалгүй шүршүүр онгойж, дарааллын эхний хүн шүршүүрт ордог. Хэсэг хугацааны дараа эхний хүн уснаас гарч, дараагийн хүн нь шүршүүрт ордог. Дарааллын хүн бүр шүршүүрт ортол энэ үйл явц үргэлжилсээр байна.

Мэдээж шүршүүрт орсон хүнд хугацаа хэрэгтэй учраас оюутнууд дараалалд хүлээх зуураа хоорондоо ярилцдаг. Хугацааны агшин бүрд оюутнууд хос хосоороо ярилцана: дарааллын $(2i - 1)$-р хүн дарааллын (яг энэ агшинд) $(2i)$-р хүнтэй ярилцана.

Энэ үйл явцын талаар илүү дэлгэрэнгүй авч үзье. Хүмүүсийг $1$-ээс $5$ хүртэл дугаарлая. Дараалал эхлээд $[2,3,1,5,4]$ ($2$ дугаар хүн дарааллын эхэнд байна) байсан гэж үзье. Шүршүүр онгойхоос өмнө 2-р хүн 3-р хүнтэй, 1-р хүн 5-р хүнтэй ярилцаж харин $4$-р хүн хэнтэй ч ярилцаагүй байна. Дараа нь шүршүүр онгойж $2$-р хүн шүршүүрт орно. $2$-р хүн шүршүүрт орж байх үед $3$-р хүн $1$-р хүнтэй, $5$-р хүн $4$-р хүнтэй ярилцана. Дараа нь $3$-р хүн шүршүүрт ороод $1$-р хүн $5$-р хүнтэй ярилцаж, $4$-р хүн хэнтэй ч ярилцаагүй байна. Дараа нь $1$-р хүн шүршүүрт орж, энэ үед $5$ болон $4$-р хүн ярилцана. Ингээд $5$-р хүн шүршүүрт орж дараа нь $4$-р хүн шүршүүрт орно.

Бидний мэдэж байгаачлан $i$ болон $j$-р оюутнууд ярилцаж байгаа бол $i$-р оюутны аз жаргал $g_{ij}$-р өсөх ба $j$-р оюутны аз жаргал $g_{ji}$-р өснө. Таны даалгавар бол хамгийн сүүлд бүх оюутнуудын нийт аз жаргал хамгийн их байхаар оюутнуудын анхны дарааллыг олох явдал юм. Зарим хос оюутнууд хэд хэдэн удаа ярилцаж болохыг анхаарна уу. Дээрх жишээн дээр $1$ болон $5$-р оюутнууд шүршүүр онгойход, мөн $3$-р оюутныг шүршүүрт орж байх үед ярилцдаг.

Оролт

Оролт нь $5$ мөр агуулах ба мөр бүр нь зайгаар тусгаарлагдсан таван бүхэл тоонууд агуулна: $i$-р мөрийн $j$-р тоо нь $g_{ij}$ ($0 ≤ g_{ij} ≤ 10^{5}$) байна. Бүх $i$-н хувьд $g_{ii} = 0$ байна.

Оюутнуудыг $1$-ээс $5$ хүртэл дугаарлагдсан гэж үзнэ.

Гаралт

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

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

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

Оролт
0 0 0 0 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
7 0 0 0 0
Гаралт
32
Оролт
0 43 21 18 2
3 0 21 11 65
5 2 0 1 4
54 62 12 0 99
87 64 81 33 0
Гаралт
620

Тэмдэглэл

Эхний жишээнд дарааллын оновчтой зохион байгуулалт нь $[2,3,1,5,4]$. Энэ тохиолдолд нийт аз жаргал нь:

$(g_{23} + g_{32} + g_{15} + g_{51}) + (g_{13} + g_{31} + g_{54} + g_{45}) + (g_{15} + g_{51}) + (g_{54} + g_{45}) = 32$ байна.

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