D. Зураг төслийн хулгай

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

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

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

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

Босогчид санаандгүйгээр холын гариг дээр Галактикийн эзэнт гүрний хэрэгцээгээр үүссэн олон өнцөгтийн маш нууц судалгааг гартаа оруулсан. Босогчид энэ олон өнцөгт шинэ үхлийн зэвсэг хөгжүүлж байна гэж үзэж байна. Олон өнцөгт нь газар доогуур сувгаар холбогдсон $n$ цөмийн хошуунаас бүрдэнэ. Сувгууд нь судалгааг удирдах лабораториудтай холбогдсон. Сувгууд нь маш сайн хамгаалагдсан ба $i$ болон $j$ хошуу хоорондох суваг нь $c_{i, j}$ дайны роботуудаар хамгаалагдсан.

Босогчид олон өнцөгтийн төлөвлөгөөг судалсан ба ер бусын бүтцийг нь анзаарсан. Дурын $k$ элементтэй хошуунуудын $S$ бүрдлийн хувьд $S$-ийн бүх хошуутай шууд хоолойгоор холбогдсон яг нэг хошуу байна гэдгийг тогтоосон (бид энэ хошууг $S$-тэй хөрш гэж нэрлэнэ). Үүнийг авч үзээд босогчид дараах зүйлсийг хийхээр шийдсэн:

  1. тэд $k$ элементтэй хошуунуудын бүрдэл $S$-г сонгоно;
  2. бүлэг тагнуулч агаараас $S$-н хошуу бүррүү газардана;
  3. бүлэг бүр $S$-тэй хөрш хошууруу чиглэсэн харгалзах хоолойны дагуу явна (тагнуулчид яваад лабораториудыг шалгах ба зэвсгийн зураг төслийн бүх тэмдэглэгээг үзнэ);
  4. $S$-тэй хөрш хошуун дээр бүлгүүд цуглан хөлөгт суугаад ниснэ.

Энэ ажиллагааны гол аюул нь тагнуулуудын явах хоолойнуудыг хамгаалж байгаа нийт роботуудын тоо юм. Ажиллагааны аюул нь мэдээж зөвхөн $S$ бүрдлийг хэрхэн сонгохоос л шууд хамаарахаар байна. Босогчид яг аль хошуунуудруу тагнуулуудыг илгээхээ шийдээгүй байна. Гэхдээ тэд тагнуулын бүлгүүдэд зэвсгийг нь бэлдэж эхлэхийг хүсч байна. Үүнийг хийхийн тулд босогчид $S$ бүрдлийг сонгох бүх замуудын хувьд харгалзах үйлдлүүдийн аюулын математик дунджийг мэдэх хэрэгтэй байна. Энэ асуудлыг шийдэж босогчдод Бүгд найрамдах улсын сайн сайхныг хамгаалахад туслана уу!

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $k$ ($2 ≤ n ≤ 2000$, $1 ≤ k ≤ n - 1$) байх ба харгалзан хошуунуудын тоо болон тагнуулын бүлгүүдийн тоо байна. Дараагийн $n - 1$ мөрөнд олон өнцөгтийн төлөвлөгөөг тодорхойлно. $i$-р мөрөнд $n - 1$ бүхэл тоон утга $c_{i, i + 1}, c_{i, i + 2}, ..., c_{i, n}$ байх ба эдгээр нь харгалзах хоолойнуудыг хамгаалж байгаа роботуудын тоо юм (-$1 ≤ c_{i, j} ≤ 10^{9}$; хэрвээ $c_{i, j} = $ -$1$ байвал $i$ болон $j$ хошуунуудын хооронд хоолой байхгүй гэсэн үг). Бүх хоолой хос чиглэлтэй буюу бид $c_{i, j} = c_{j, i}$ гэж үзэж болно. Ямар ч хоолой хошууг өөртэй нь холбохгүй. Олон өнцөгтийн төлөвлөгөө нь бодлогын нөхцөлүүдтэй тохирох нь тодорхой.

Гаралт

Тагнуулын ажиллагааны дундаж аюулыг доод бүхэл тооруу нь бүхэлдэж гарсан тоог хэвлэнэ үү. Өгөгдсөн хязгаард бодлогын хариу нь үргэлж стандарт 64 битийн бүхэл тоон өгөгдлийн төрөлд таарна.

C++ хэлэнд 64 битийн бүхэл тоонуудыг бичихдээ %lld тодорхойлогчийг битгий ашиглаарай. Оронд нь $cout$ урсгал эсвэл $%I64d$ тодорхойлогчийг ашиглаарай.

Орчуулсан: Г.Мэндбаяр

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

Оролт
6 1
-1 -1 -1 8 -1
-1 5 -1 -1
-1 -1 3
-1 -1
-1
Гаралт
5
Оролт
3 2
10 0
11
Гаралт
14

Тэмдэглэл

Эхний жишээн дээр хошуунуудын нэг-элемент бүхий 6 бүрдэл байна. ${1}$, ${5}$ бүрдлүүдийн хувьд ажиллагааны аюул нь 8-тай тэнцүү, ${3}$, ${6}$ бүрдлүүдийн хувьд 3 байна, харин ${2}$, ${4}$ бүрдлүүдийн хувьд 5 байна. Ингээд математик дундаж нь байна.

Хоёр дахь жишээнд хошуунуудын хоёр-элемент бүхий 3 бүрдэл байна. Эдгээр нь ${1, 3}$ (аюул нь 21), ${1, 2}$ (аюул нь 11), ${2, 3}$ (аюул нь 10). Ингээд ажиллагааны дундаж аюул нь байна.

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