Masala #0929

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 60 %
4.0 (Baholar 4)
14

  

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 nn ta bo'limdan iborat devor bor. Ayni paytda ii-bo'limda aia_i ta kamonchi elflar joylashgan. Malumki ii-bo'limda joylashgan har bir kamonchi rr dan ortiq bo'lmagan masofalardagi bo'limga hujim qilayotgan dushmanga qarshi o'q uzaoladi, ya'ni j(ijr)j(|i-j|\leq r) raqamli bo'limlarga o'q uzaoladi. 

ii-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 kk ta kamonchilar zaxirasi mavjud. Sizning vazifangiz mudofa rejasining ishonchliligini maksimal qilishdan iborat.


Kiruvchi ma'lumotlar:

Dastlabki satrda n,r,k(1n500000,0rn,0k1018)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 nn ta butun son ai(0ai109)a_i(0\leq a_i\leq 10^9) ii-bo'limda joylashgan kamonchilar soni.


Chiquvchi ma'lumotlar:

Yagona butun sonni chop eting - mudofa rejasi ishonchliligining maksimal mumkun bo'lgan qiymati, ya'ni zaxiradagi kk ta kamonchilarni optimal joylashtirish orqali devorning bir qismini himoya qilishning maksimal mumkun bo'lgan minimal qiymatini chop eting.


Misollar
# input.txt output.txt
1
4 1 2
5 1 1 2
5
2
5 0 6
5 4 3 4 9
5
Izoh:

1-test: Jami bo'li 44 ta bo'lim devorni himoyalaydi.
11-bo'limda 55 ta kamonchi bor va bu bo'limga 22-bo'limdagi kamonchilar yordam beraoladi, sababi 12r|1-2|\leq r va bu bo'limning himoyasi 5+1=65+1=6 ga teng.
22-bo'limdiki esa 5+1+1=75+1+1=7 ga teng.
33-bo'limniki esa 1+1+2=41+1+2=4 ga teng.
44-bo'limniki 1+2=31+2=3 ga teng.
Siz agar uchunchi bo'limga zaxiradagi 22 ta kamonchini joyllashtirsangiz ikkinchi bo'liming himoyasi 99 ga, uchunchi bo'limning himoyasi 66 ga va to'rtinchi bo'limning himoyasi 55 ga o'zgaradi. Shunday qilib bo'limlar himoyalarini maksimal qilganimizdan so'ng, barcha bo'limlar uchun minimal himoyani tanlaymiz. min(6,9,6,5)=5min(6, 9, 6, 5) = 5 bu qal'a devornig himoyasini ifodalaydi.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin