Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Районы Байтландии
Байтландия - замечательная страна, обладающая живописной природой и расположенная в центре континента. Основным источником дохода для населения страны является транзит, так как через страну проходит автомагистраль международного значения МО, вдоль которой расположены все N городов Байтлапдии.
До недавних времен в стране не существовало административно-территориального деления, то есть отсутствовали районы, области и округа. Последние несколько десятков лет численность байтландцев значительно выросла, поэтому управлять страной стало сложно. Правительство страны в целях упрощения административного управления приняло решение разделить Байтландию на К районов. Каждый район включает один или более городов. Кроме этого, каждый город должен принадлежать одному из К районов. Правительство Байтлапдии постановило, что деление на районы должно быть таким, что каждому району отводится определенный отрезок автомагистрали, поэтому все города, расположенные вдоль этого отрезка, принадлежат данному району. То есть, если город В находится между городами А и С и города А и С принадлежат одному району, то и город В принадлежит этому району.
Известно, что численность населения каждого из N городов Байтландии равна Аь поэтому для каждого из К районов несложно определить Sj - численность населения соответствующего района, равную суммарной численности населения всех городов, принадлежащих этому району. Правительству Байтландии важно, чтобы численность населения одного района незначительно отличалась от численности населения другого района. Для этого академия наук Байтландии разработала специальный показатель административно-территориального деления S, равный сумме чисел (Sj - Sj) для всех таких пар (i, j) что 1 < i < j < К.



Ученым Байтландии удалось доказать, что чем меньше показатель административно-территориального деления S, тем более близки между собой районы по численности населения. Ваша задача - определить минимальный из возможных показателей административно-территориального деления S. который может быть достигнут разделением N городов Байтландии на К районов.
Входные данные:
Первая строка входного фарт содержит два целых числа, разделенных одним пробелом, это числа N и К (1 < N < 500, 1 < К < 100, К < N) соответственно.
Вторая строка входного файла содержит N целых чисел Aj (] < Aj < 65536) -численность населения i-ro города. Числа разделены одиночными пробелами.
Выходные данные:
Выходной файл должен содержать одно целое число - минимальный из возможных показатслей административно-территориального деления.

Примеры:
input.txt output.txt
1 6
350 60 90 15 70 20
650
2 7
21 2 3 4 5 6 7
4

Сложность задачи: 50%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 34, зарегистрированных 1:
375444700665,
[Данные за последние 5 минут]