Taxtalar

time limit per test 1.0 second

Sizga n ta taxtani uzunliklari massiv sifatida berilgan. Sizning vazifangiz shunday k ta taxtani kesib olishki, shu k ta kesib olingan taxtani uzunliklari bir hil bo’lsin hamda kesib   olingan uzunlik maksimal bo’lsin. Shu maksimal uzunlikni toping. Yaxshiroq tushunish uchun izohga qarang. 

 

Kiruvchi ma’lumotlar:

Birinchi qatorda n, k sonlari (1 ≤ n,k 105).

Ikkinchi qatorda massiv elementlari beriladi (1 ≤ a[i] 109)

Chiquvchi ma’lumotlar:

Yagona qatorda masala yechimi chiqaring.

 

Izoh:

1 – chi  testda uzunliki 4 dan katta bo’lgan 4 ta taxtani kesib olib bo’lmaydi.

1 – chi taxta orqali uzunliki 4 bo’lgan taxta kesib olib bo’lmaydi.

2 – chi taxta orqali uzunliki 4 bo’lgan 2 ta taxtani kesib olish mumkin.

3 – chi taxta orqali 0.

4 – chi taxta orqali 1.

5 – chi taxta orqali 1.

2 + 1 + 1 = 4.

Masalan endi uzunliki 5 bo’lgan taxtalardan qanchani kesib olib bo’lishini ko’rsak.

1 – chi taxtadan 0.

2 – chidan 1.

        3 – chidan 0.

           4 – chidan 1.

           5 – chidan 0.

           1 + 1 = 2 < 4.

2 – chi testdan uzunliki 2 bo’lgan 6 ta taxtani kesib olib bo’ladi faqat. 1 – chidan 0, 2 – chidan 1, 3 – chidan 1, 4 – chidan 2, 5 – chidan 2. 1 + 1 + 2 + 2 = 6.

 


Autor: - Nazarbek Boltabayev

For send solution