Masala #0929
Qal'a himoyasi
Berlandiya mamlakatida bir qal'a mavjud. Bu qal'aga dushman hujum qilmoqchi. Siz qal'ani yovuz dushmanlarning hujumidan himoya qilish uchun kamonchi elflarni boshqarishingiz kerak. Qal'a uch tomondan o'tib bo'lmas to'siqlar bilan himoyalangan va qolgan to'rtinchi kirish tomonida esa \(n\) ta bo'limdan iborat devor bor. Ayni paytda \(i\)-bo'limda \(a_i\) ta kamonchi elflar joylashgan. Malumki \(i-\)bo'limda joylashgan har bir kamonchi \(r\) dan ortiq bo'lmagan masofalardagi bo'limga hujim qilayotgan dushmanga qarshi o'q uzaoladi, ya'ni \(j(|i-j|\leq r)\) raqamli bo'limlarga o'q uzaoladi.
\(i-\)bo'limning xafsizligi - bu qisimga hujum qilayotgan dushmanlarga o'q uzishi mumkin bo'lgan kamonchilarning umumiy soniga teng. Mudofa rejasining ishonchliligi har qanday bo'lim xafsizligining minimal qiymati hisoblanadi.
Dushman hujum qilishiga juda oz vaqt qoldi va siz bo'limlardagi kamonchilarni qayta joylashtirib chiqish uchun vaqingiz yo'q. Biroq sizda bo'limlarga joylashtirish uchun zaxirada \(k\) ta kamonchilar zaxirasi mavjud. Sizning vazifangiz mudofa rejasining ishonchliligini maksimal qilishdan iborat.
Dastlabki satrda \(n,r,k(1\leq n\leq 500000, 0\leq r \leq n, 0\leq k\leq 10^{18})\) mos ravshda devorni tashkil etuvchi bo'limlar soni, har bir kamonchi o'q uzishi mumkun bo'lgan maksimal masofa va zaxiradagi kamonchilar soni. Kiyingi satrda \(n\) ta butun son \(a_i(0\leq a_i\leq 10^9)\) \(i-\)bo'limda joylashgan kamonchilar soni.
Yagona butun sonni chop eting - mudofa rejasi ishonchliligining maksimal mumkun bo'lgan qiymati, ya'ni zaxiradagi \(k\) ta kamonchilarni optimal joylashtirish orqali devorning bir qismini himoya qilishning maksimal mumkun bo'lgan minimal qiymatini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 1 2 5 1 1 2 |
5 |
| 2 |
5 0 6 5 4 3 4 9 |
5 |
1-test: Jami bo'li \(4\) ta bo'lim devorni himoyalaydi.
\(1-\)bo'limda \(5\) ta kamonchi bor va bu bo'limga \(2-\)bo'limdagi kamonchilar yordam beraoladi, sababi \(|1-2|\leq r\) va bu bo'limning himoyasi \(5+1=6\) ga teng.
\(2-\)bo'limdiki esa \(5+1+1=7\) ga teng.
\(3-\)bo'limniki esa \(1+1+2=4\) ga teng.
\(4-\)bo'limniki \(1+2=3\) ga teng.
Siz agar uchunchi bo'limga zaxiradagi \(2\) ta kamonchini joyllashtirsangiz ikkinchi bo'liming himoyasi \(9\) ga, uchunchi bo'limning himoyasi \(6\) ga va to'rtinchi bo'limning himoyasi \(5\) ga o'zgaradi. Shunday qilib bo'limlar himoyalarini maksimal qilganimizdan so'ng, barcha bo'limlar uchun minimal himoyani tanlaymiz. \(min(6, 9, 6, 5) = 5\) bu qal'a devornig himoyasini ifodalaydi.
Telegram kanalimizga obuna bo'ling