Codeforces Round 544 (Div. 3) |
---|
Закончено |
Вы — университетский тренер. Всего в университете $$$n$$$ студентов под Вашим надзором, умение программировать $$$i$$$-го студента равно $$$a_i$$$.
Вы хотите составить $$$k$$$ команд для другого нового соревнования по программированию. Как Вы знаете, чем больше студентов на соревновании — тем больше шансов победить! Поэтому Вы хотите составить не более $$$k$$$ непустых команд (и хотя бы одну) таким образом, чтобы суммарное число студентов в них было максимально возможно. Но Вы также знаете, что каждая команда должна быть сбалансированной. Это означает, что умение программировать каждой пары студентов в каждой команде должно отличаться не более, чем на $$$5$$$. Команды являются независимыми друг от друга (это означает, что разница в умении программировать двух студентов из двух разных команд не имеет значения).
Возможно, что некоторые студенты не будут включены ни в какие команды вообще.
Ваша задача — найти максимально возможное суммарное число студентов в не более, чем $$$k$$$ (и хотя бы одной) непустых сбалансированных командах.
Если Вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете отправлять свой код.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 5000$$$) — количество студентов и количество команд, соответственно.
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ означает умение $$$i$$$-го студента программировать.
Выведите одно целое число — максимально возможное суммарное число студентов в не более, чем $$$k$$$ (и хотя бы одной) непустых сбалансированных командах.
5 2 1 2 15 15 15
5
6 1 36 4 1 25 9 16
2
4 4 1 10 100 1000
4
Название |
---|