Masala #0677
Tug’ilgan kun #4
Akrom bugun tug’ilgan kunini nishonlamoqda va shu munosabat bilan o’zining ta do’stini kechki ovqatga taklif qildi. Kechki ovqat stolida bir qatorda terilgan ta ovqat bo’lib, - ovqatni yegan odamni kayfiyati 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 va mehmonlar soni kiritiladi . Keyingi qatorda ta butun son - kiritiladi .
1-subtask(5 ball):
2-subtask(6 ball): Ko’pi bilan bitta ovqat uchun bo’ladi,
3-subtask(10 ball):
4-subtask(15 ball):
5-subtask(26 ball):
6-subtask(38 ball):
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.