Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2298. Школьный поход
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 02/10/2016 | Личное первенство по спортивному программированию (G) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Джимбо и Нед являются организаторами школьного похода.
Выбранный ими маршрут привел бойскаутов к старому канатному мосту, который пугает некоторых школьников.
Поэтому Джибмо нужно придумать, как быстро преодолеть это препятствие и продолжить поход.
Школьники должны переходить мост в том порядке, в котором подошли к мосту, при этом на мост
должны заходить группами от 1 до `M` человек, чтобы мост не рухнул под их тяжестью.
Группа движется по мосту вместе и переходит его за время перехода самого медленного из членов группы.
Напишите программу, которая найдет оптимальный план разбиения на группы, минимизирующий
суммарное время перехода через мост.
Первая строка ввода содержит два целых числа – количество школьников `N` (`1\ ≤\ N\ ≤\ 100000`) и
максимальный размер группы `M` (`1\ ≤\ M\ ≤\ 20`). Следующая строка содержит `N` целых чисел в диапазоне от 1
до 1000 – время на переход моста для каждого школьника.
В первой строке вывести одно число – минимальное суммарное время перехода через мост.
Во второй строке вывести размеры групп, на которые нужно разбить школьников.
Пример ввода
5 2 1 7 5 4 6
Пример вывода
14 1 2 2
