Masala #1053

Xotira 64 MB Vaqt 1000 ms
14

Karimjon va qismlarga bo`lish

Karimjonga yaqinda sovg`a sifatida uzunligi \(n\) bo`lgan \(A\) butun musbat sonlar massivi sovg`a qilishdi. Karimjon do`sti Asilbek bilan birga o`ynashi uchun ko`proq massivlar kerak, shuning uchun ham u o`zining \(A\) massivini aynan \(k\) ta bo`lakga ajratmoqchi. Bunda har bir bo`lak \(A\) ning qism massivi bo`lishi shart.

Karimjon massivning chiroyliligiga ham e'tibor beradi. Uning fikricha massiv chiroyliligi bu \(X\) ning turli xil tub bo`luvchilari sonidir. Bu yerda esa \(X\) shu massivning barcha elementlari ko`paytmasi. Misol uchun \([2,10,77]\) massivi uchun \(X = 1540\). \(X\) ning turli xil tub bo`luvchilari soni esa \(4\) ta. Demak massiv chiroyliligi \(4\) ga teng.

Karimjon \(A\) massivni shunday \(k\) ta massivga bo`lishga qaror qildiki, hosil bo`lgan massivlar ichida maksimal chiroylilikga ega massiv chiroyliligi minimal bo`lsin. Siz shu qiymatni topishingiz lozim.


Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - \(n,k(1 \leq k \leq n \leq 2*10^5)\) \(A\) massiv uzunligi va bo`laklar soni kiritiladi.

Ikkinchi qatorda \(n\) ta butun son - \(A[i](1 \leq A[i] \leq 1000)\) massiv elementlari kiritiladi.


Chiquvchi ma'lumotlar:

Yagona qatorda bitta butun son, masalaga javobni chiqaring.


Misollar
# input.txt output.txt
1
3 2
6 7 110
3
2
5 1
10 18 19 3 77
6
Izoh:

1-testda massivni 2 xil usulda bo`lsa bo`ladi.

- Birinchi usul:  \([6],[7,110]\). Bunda \(X_1 = 6\) va \(X_2 = 770\). Demak birinchi massiv chiroyliligi \(2\), ikkinchi massiv chiroyliligi esa \(4\). Maksimal qiymatlisi \(4\).

- Ikkinchi usul:  \([6,7],[110]\). Bunda \(X_1 = 42\) va \(X_2 = 110\). Demak birinchi massiv chiroyliligi \(3\), ikkinchi massiv chiroyliligi esa \(3\). Maksimal qiymatlisi \(3\).

Ulardan minimali esa \(3\). Demak natija ham \(3\).

Python tilida yozadiganlar uchun: PyPy orqali yechimni yuborish uni tezlashtirishi mumkin!