Masala F
Kontest Zanjiri
KhIMIO 2026 musobaqa komiteti yangi kontest tayyorlamoqda. Ular \( N \) ta masala tuzishdi. Tajribalariga asoslanib, ba'zi masalalar boshqalaridan qiyinroq ekanligi ma'lum — bu munosabatlar yo'naltirilgan graf shaklida berilgan: \( u \) dan \( v \) ga yo'nalgan qirra mavjud bo'lsa, \( u \)-masala \( v \)-masaladan qat'iy osonroq degan ma'noni anglatadi.
Har bir masalaning \( q_i \) qiziqarlilik balli bor. Bu ball manfiy ham bo'lishi mumkin — zerikarli yoki takroriy mavzu kontestning umumiy sifatini pasaytiradi.
Komitet kontestni aynan \( K \) ta masaladan tuzmoqchi, va bu masalalar qiyinlik darajasi bo'yicha o'sish tartibida joylashtirilishi kerak. Barcha bunday yo'llar ichidan ular umumiy qiziqarlilik bali eng katta bo'lganini tanlashni xohlaydi.
Aynan \( K \) ta masaladan iborat to'g'ri kontestning maksimal umumiy qiziqarlilik balini toping. Agar bunday kontest tuzish mumkin bo'lmasa, IMPOSSIBLE deb chiqaring.
Birinchi qatorda uchta butun son \( N \), \( M \), \( K \) — masala-nomzodlar soni, "qiyinroq" munosabatlar soni va kontest uzunligi.
Ikkinchi qatorda \( N \) ta butun son \( q_1, q_2, \ldots, q_N \) — har bir masalaning qiziqarlilik bali.
Keyingi \( M \) qatorda ikkitadan butun son \( u \) va \( v \) — \( u \)-masala \( v \)-masaladan qat'iy osonroq ekanligi.
\( 1 \le N \le 1000 \)
\( 0 \le M \le 5000 \)
\( 1 \le K \le N \)
\( -10^9 \le q_i \le 10^9 \)
Grafda sikl mavjud emasligi kafolatlanadi.
Uzunligi aynan \( K \) bo'lgan yo'lning maksimal umumiy qiziqarlilik balini chop eting.
Agar bunday yo'l mavjud bo'lmasa, IMPOSSIBLE deb chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 5 3 8 3 5 7 -2 1 2 1 3 2 4 3 4 3 5 |
20 |
| 2 |
4 3 5 1 2 3 4 1 2 2 3 3 4 |
IMPOSSIBLE |
| 3 |
6 5 3 0 100 1 2 3 -50 1 2 1 3 3 4 4 5 3 6 |
6 |
1-test: \( N = 5 \) ta masala, \( q = [8, 3, 5, 7, -2] \), \( K = 3 \). Graf quyidagicha:
1(8)
/ \
2(3) 3(5)
\ / \
4(7) 5(-2)
Uzunligi 3 bo'lgan barcha yo'llar:
- \( 1 \to 2 \to 4 \): ball \( 8 + 3 + 7 = 18 \)
- \( 1 \to 3 \to 4 \): ball \( 8 + 5 + 7 = 20 \) (maksimal)
- \( 1 \to 3 \to 5 \): ball \( 8 + 5 + (-2) = 11 \)
Javob: 20.
2-test: 4 ta masala zanjir bo'lib ulangan: \( 1 \to 2 \to 3 \to 4 \). Eng uzun yo'l uzunligi 4, lekin \( K = 5 \) kerak. To'g'ri kontest tuzib bo'lmaydi, javob: IMPOSSIBLE.
3-test: \( N = 6 \), \( q = [0, 100, 1, 2, 3, -50] \), \( K = 3 \). Graf:
1(0) -> 2(100) [o'tuvchi qirra yo'q]
1(0) -> 3(1) -> 4(2) -> 5(3)
-> 6(-50)
2-masala jozibali ko'rinadi (\( q_2 = 100 \)), lekin \( 1 \to 2 \) yo'li uzunligi 2 va 2-masaladan chiquvchi qirra yo'q — uni \( K = 3 \) ga yetkazib bo'lmaydi.
Uzunligi 3 bo'lgan barcha to'g'ri yo'llar:
- \( 1 \to 3 \to 4 \): ball \( 0 + 1 + 2 = 3 \)
- \( 1 \to 3 \to 6 \): ball \( 0 + 1 + (-50) = -49 \)
- \( 3 \to 4 \to 5 \): ball \( 1 + 2 + 3 = 6 \) (maksimal)
Yo'l manba (kirish darajasi 0 bo'lgan) tugundan boshlanishi shart emas — istalgan joydan boshlanishi mumkin.
Javob: 6.
Telegram kanalimizga obuna bo'ling