Masala #UF9PN0G4ZH

Xotira 32 MB Vaqt 1000 ms Qiyinchiligi 30 %

#Binar qidiruv

Taxtalarni kesish

Sizda n taxta bor, ularning uzunliklari berilgan. Siz arraning balandligini h qilib tanlaysiz.

Har bir taxta a[i] uchun: agar a[i] > h bo‘lsa, a[i] - h qismi kesiladi.
Agar a[i] ≤ h bo‘lsa, u taxtadan hech narsa chiqmaydi.

Sizga m uzunlikdagi yog‘och kerak. Shunday qilib, siz arraning balandligini maksimal tanlashingiz kerakki, kesilgan bo‘laklarning yig‘indisi kamida m ga teng bo‘lsin.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son n va m (1 ≤ n ≤ 10^6, 1 ≤ m ≤ 10^12).
Ikkinchi qatorda n ta butun son a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^9) beriladi.

Chiquvchi ma'lumotlar:

Bitta butun son chiqaring — arraning maksimal balandligi h

Misollar

#	input.txt	output.txt
1	4 7 20 15 10 17	15

Izoh:

1-test. h = 15 bo‘lsa: 20 → 5, 17 → 2, 15 → 0, 10 → 0. Yig‘indi = 7. Agar h = 16 bo‘lsa, faqat 20 → 4, 17 → 1, yig‘indi = 5 < 7. Demak javob = 15

Telegram Facebook

Yechimini yuborish

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