Masala #0679
Tug’ilgan kun #6
Akrom bugun tug’ilgan kunini nishonlamoqda va shu munosabat bilan o’zining \(k\) ta do’stini kechki ovqatga taklif qildi. Kechki ovqat stolida bir qatorda terilgan \(n\) ta ovqat bo’lib, \(i\)- ovqatni yegan odamni kayfiyati \(a_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.
Birinchi qatorda ovqatlar soni \(n\) va mehmonlar soni \(k\) kiritiladi \((1 ≤ k ≤ n ≤ 10^5)\). Keyingi qatorda \(n\) ta butun son - \(a_1, a_2, ..., a_n\) kiritiladi \((-10^9 ≤ a_i ≤ 10^9)\).
1-subtask(5 ball): \(a_i ≥ 0, n ≤ 10^5\)
2-subtask(6 ball): Ko’pi bilan bitta ovqat uchun \(a_i ≤ 0\) bo’ladi, \(n ≤ 10^5\)
3-subtask(10 ball): \(k = 1\)
4-subtask(15 ball): \(1 ≤ k ≤ n ≤ 80\)
5-subtask(26 ball): \(1 ≤ k ≤ n ≤ 2000\)
6-subtask(38 ball): \(1 ≤ k ≤ n ≤ 10^5\)
Bitta butun son - masalaning javobini chiqaring.
| # | 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 |
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.
Telegram kanalimizga obuna bo'ling