Masala #0677

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

  

Tug’ilgan kun #4

Akrom bugun tug’ilgan kunini nishonlamoqda va shu munosabat bilan o’zining kk ta do’stini kechki ovqatga taklif qildi. Kechki ovqat stolida bir qatorda terilgan nn ta ovqat bo’lib, ii- ovqatni yegan odamni kayfiyati aia_i ga o’zgaradi. Endi Akrom bu ovqatlarni do’stlariga bo’lib berishi kerak.

Har bir mehmon stolda ketma-ket joylashgan bir nechta ovqatni yeyishi yoki umuman ovqat yemasligi ham mumkin. Ammo bitta ovqatni faqat bir kishi yeya oladi xolos. Akrom mehmonlarga ovqatlarni shunaqangi bo’lib berishi kerakki, ovqatlanib bo’lgandan so’ng mehmonlarning umumiy kayfiyati maksimal bo’lsin. Bunda Akromga yordam bering.


Kiruvchi ma'lumotlar:

Birinchi qatorda ovqatlar soni nn va mehmonlar soni kk kiritiladi (1kn105)(1 ≤ k ≤ n ≤ 10^5). Keyingi qatorda nn ta butun son - a1,a2,...,ana_1, a_2, ..., a_n kiritiladi (109ai109)(-10^9 ≤ a_i ≤ 10^9).

1-subtask(5 ball): ai0,n105a_i ≥ 0, n ≤ 10^5
2-subtask(6 ball): Ko’pi bilan bitta ovqat uchun ai0a_i ≤ 0 bo’ladi, n105n ≤ 10^5
3-subtask(10 ball): k=1k = 1
4-subtask(15 ball): 1kn801 ≤ k ≤ n ≤ 80
5-subtask(26 ball): 1kn20001 ≤ k ≤ n ≤ 2000
6-subtask(38 ball): 1kn1051 ≤ k ≤ n ≤ 10^5


Chiquvchi ma'lumotlar:

Bitta butun son - masalaning javobini chiqaring.


Misollar
# input.txt output.txt
1
6 1
1 -2 3 -1 5 -6
7
2
6 2
1 2 3 -10 5 6
17
3
6 4
-1 -2 -1 0 -5 -1
0
Izoh:

Birinchi misolda yagona mehmon uchun [3, -1, 5] oraliqni bersak optimal bo’ladi.
Ikkinchi misolda 2 ta mehmonlar uchun [1, 2, 3] va [5, 6] oraliqdagi ovqatlarni bersak, ularning umumiy kayfiyati 6 + 11 = 17 bo’ladi.
Uchinchi misolda hech qaysi mehmonga ovqat bermagan ma’qul.

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