Masala D
Unutilgan indekslar
Sizga uzunligi \(n\) bo'lgan massiv berilgan:
\[ a_1,a_2,\ldots,a_n \]
Har bir indeks \(i\) uchun \(c_i\) narx ham beriladi. Siz massivdagi istalgan indekslarni unutib yuborishingiz mumkin. Agar \(i\)-indeks unutilsa, buning uchun \(c_i\) narx to'lanadi. Unutilmagan indekslar chapdan o'ngga qaralganda quyidagi shart bajarilishi kerak:
\[ a_j-a_i\ge d \]
Bu yerda \(i\) va \(j\) — ikkita ketma-ket unutilmagan indeks va \(i \lt j\). Boshqacha aytganda, qolgan elementlar indeks tartibini saqlagan holda har safar kamida \(d\) ga oshib borishi kerak. Sizning vazifangiz — massivni shartga mos holatga keltirish uchun to'lanadigan eng kichik umumiy narxni topish. Kamida bitta indeks unutilmay qolishi kerak.
Birinchi qatorda bitta butun son \(t\) — testlar soni beriladi. Har bir test uchun birinchi qatorda ikkita butun son \(n\) va \(d\) beriladi. Ikkinchi qatorda \(n\) ta butun son beriladi:
\[ a_1,a_2,\ldots,a_n \]
Uchinchi qatorda \(n\) ta butun son beriladi:
\[ c_1,c_2,\ldots,c_n \]
Bu yerda \(c_i\) — \(i\)-indeksni unutish narxi. Cheklovlar:
\[ \begin{aligned} 1&\le t\le 1000,\\ 1&\le n\le 2\cdot 10^5,\\ 1&\le \sum n\le 2\cdot 10^5,\\ 0&\le d\le 10^9,\\ 1&\le a_i,c_i\le 10^9. \end{aligned} \]
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 5 3 4 1 7 5 10 8 5 6 4 7 4 2 5 4 3 2 10 20 30 40 |
9 60 |
Birinchi testda \(2\)- va \(4\)-indekslarni unutish mumkin. Qolgan elementlar:
\[ 4,7,10 \]
Ular orasidagi farqlar:
\[ 7-4=3,\qquad 10-7=3 \]
Demak, shart bajariladi. To'langan narx:
\[ c_2+c_4=5+4=9 \]
Ikkinchi testda massiv kamayib boradi:
\[ 5,4,3,2 \]
\(d=2\) bo'lgani uchun bir nechta elementni indeks tartibida qoldirish foyda bermaydi. Faqat \(4\)-indeksni qoldirib, qolganlarini unutish optimal. Narx:
\[ c_1+c_2+c_3=10+20+30=60 \]
Telegram kanalimizga obuna bo'ling