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 ta bo'limdan iborat devor bor. Ayni paytda -bo'limda ta kamonchi elflar joylashgan. Malumki bo'limda joylashgan har bir kamonchi dan ortiq bo'lmagan masofalardagi bo'limga hujim qilayotgan dushmanga qarshi o'q uzaoladi, ya'ni raqamli bo'limlarga o'q uzaoladi.
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 ta kamonchilar zaxirasi mavjud. Sizning vazifangiz mudofa rejasining ishonchliligini maksimal qilishdan iborat.
Dastlabki satrda 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 ta butun son bo'limda joylashgan kamonchilar soni.
Yagona butun sonni chop eting - mudofa rejasi ishonchliligining maksimal mumkun bo'lgan qiymati, ya'ni zaxiradagi 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 ta bo'lim devorni himoyalaydi.
bo'limda ta kamonchi bor va bu bo'limga bo'limdagi kamonchilar yordam beraoladi, sababi va bu bo'limning himoyasi ga teng.
bo'limdiki esa ga teng.
bo'limniki esa ga teng.
bo'limniki ga teng.
Siz agar uchunchi bo'limga zaxiradagi ta kamonchini joyllashtirsangiz ikkinchi bo'liming himoyasi ga, uchunchi bo'limning himoyasi ga va to'rtinchi bo'limning himoyasi ga o'zgaradi. Shunday qilib bo'limlar himoyalarini maksimal qilganimizdan so'ng, barcha bo'limlar uchun minimal himoyani tanlaymiz. bu qal'a devornig himoyasini ifodalaydi.