Университетская команда
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Ваш университет вовсю готовится к новому сезону командных олимпиад. Как несложно догадаться, для этого необходимо собрать команду, которая будет представлять учебное заведение.
Всего в университете учатся n студентов, i-й из них имеет силу ai. Для участия в олимпиадах необходимо выбрать ровно k людей и расположить их в каком‑то порядке. Пусть были выбраны студенты с номерами i1, i2, ... , ik (именно в таком порядке). Тогда слабость команды равна |ai2−ai1|+ |ai3−ai2|+ ...+|aik−aik−1|. Иначе говоря, слабость команды равна сумме модулей разностей сил соседних участников команды, если их расположить в выбранном порядке. Обратите внимание, что порядок студентов вы выбираете сами.
Администрация университета просит вас определить минимально возможную слабость команды.
Формат входных данных
Первая строка содержит одно целое число n (1⩽n⩽100 000) — количество студентов, обучающихся в университете.
Вторая строка содержит одно целое число k (1⩽k⩽n) — количество людей в составе команды.
Каждая из следующих n строк содержит целое число ai (1⩽ai⩽109) — силу i-го студента.
Формат выходных данных
Выведите одно целое число — минимально возможную слабость команды.
Система оценки
Решения, правильно работающие при n⩽10, будут оцениваться в 25 баллов.
Решения, правильно работающие при n⩽1000, будут оцениваться в 50 баллов.
Решения, правильно работающие при ai⩽100 000, будут оцениваться в 50 баллов.
Замечание
Рассмотрим пример. Если взять студентов с номерами 1, 5 и 4 (именно в таком порядке), то слабость команды будет равна |1−1|+|2−1|=0+1=1. Можно доказать, что меньшую слабость получить не получится.
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Ваш университет вовсю готовится к новому сезону командных олимпиад. Как несложно догадаться, для этого необходимо собрать команду, которая будет представлять учебное заведение.
Всего в университете учатся n студентов, i-й из них имеет силу ai. Для участия в олимпиадах необходимо выбрать ровно k людей и расположить их в каком‑то порядке. Пусть были выбраны студенты с номерами i1, i2, ... , ik (именно в таком порядке). Тогда слабость команды равна |ai2−ai1|+ |ai3−ai2|+ ...+|aik−aik−1|. Иначе говоря, слабость команды равна сумме модулей разностей сил соседних участников команды, если их расположить в выбранном порядке. Обратите внимание, что порядок студентов вы выбираете сами.
Администрация университета просит вас определить минимально возможную слабость команды.
Формат входных данных
Первая строка содержит одно целое число n (1⩽n⩽100 000) — количество студентов, обучающихся в университете.
Вторая строка содержит одно целое число k (1⩽k⩽n) — количество людей в составе команды.
Каждая из следующих n строк содержит целое число ai (1⩽ai⩽109) — силу i-го студента.
Формат выходных данных
Выведите одно целое число — минимально возможную слабость команды.
Система оценки
Решения, правильно работающие при n⩽10, будут оцениваться в 25 баллов.
Решения, правильно работающие при n⩽1000, будут оцениваться в 50 баллов.
Решения, правильно работающие при ai⩽100 000, будут оцениваться в 50 баллов.
Замечание
Рассмотрим пример. Если взять студентов с номерами 1, 5 и 4 (именно в таком порядке), то слабость команды будет равна |1−1|+|2−1|=0+1=1. Можно доказать, что меньшую слабость получить не получится.
])