Masala #UDUVKVY9LJ
Omborlar chegarasi
To'g'ri chiziqda \(n\) ta qishloq joylashgan. \(i\)-qishloq koordinatasi \(x_i\), aholisi esa \(w_i\). Koordinatalar qat'iy o'sish tartibida beriladi.
Qishloqlarni aynan \(k\) ta ketma-ket guruhga bo'lish kerak. Har bir guruhda kamida \(A\), ko'pi bilan \(B\) ta qishloq bo'lishi shart.
Har bir guruh uchun bitta ombor tanlanadi. Ombor faqat shu guruhdagi qishloqlardan birining koordinatasida qurilishi mumkin.
Agar guruh \([l,r]\) qishloqlardan iborat bo'lsa va ombor \(p\)-qishloqda qurilsa, guruh narxi quyidagicha bo'ladi:
\[
\sum_{i=l}^{r} w_i\cdot |x_i-x_p|
\]
Har bir guruh uchun ombor joyi optimal tanlanadi. Bo'lish narxi — barcha guruhlar narxlarining maksimumi.
Shu maksimum qiymatni minimal qiling. Agar qishloqlarni berilgan shartlar bilan aynan \(k\) ta guruhga bo'lishning imkoni bo'lmasa, \(-1\) chiqaring.
Kiruvchi ma'lumotlar:
Birinchi qatorda \(t\) — testlar soni beriladi.
Har bir test quyidagi ko'rinishda beriladi:
Birinchi qatorda to'rtta butun son \(n,k,A,B\) beriladi.
Keyingi \(n\) ta qatorda ikkitadan butun son \(x_i,w_i\) beriladi.
Cheklovlar:
\[
1 \le t \le 200
\]
\[
1 \le n \le 4\cdot 10^4
\]
\[
1 \le k \le n,
\quad 1 \le A \le B \le n
\]
\[
0 \le x_1 < x_2 < \ldots < x_n \le 10^9
\]
\[
1 \le w_i \le 1000
\]
Barcha testlar bo'yicha \(\sum n \le 4\cdot 10^4\) va \(\sum(n\cdot k) \le 2\cdot 10^6\).
Chiquvchi ma'lumotlar:
Har bir test uchun alohida qatorda javobni chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 5 2 2 3 1 1 2 1 10 1 11 1 12 1 4 2 2 2 0 10 100 1 101 1 200 10 5 3 2 2 1 1 2 1 3 1 4 1 5 1 |
2 100 -1 |
Izoh:
Birinchi testda optimal bo'lish: \([1,2]\) va \([10,11,12]\). Birinchi guruh narxi \(1\), ikkinchi guruh narxi \(2\). Shuning uchun javob \(2\).
Ikkinchi testda har bir guruhda aynan \(2\) ta qishloq bo'lishi kerak. Optimal maksimum \(100\) ga teng.
Uchinchi testda \(3\) ta guruhning har birida aynan \(2\) ta qishloq bo'lishi kerak, lekin qishloqlar soni \(5\). Shuning uchun javob \(-1\).
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring,
agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin
Telegram kanalimizga obuna bo'ling