АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Соревнования
Новости Справка СДО
Регистрация  ||  Вход/выход
Забыли пароль?
Рейтинг авторов
 
О системе
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1809. Продажа огурцов

Ограничение времени: 2 сек.
Ограничение памяти:524288 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

На m дачных участках, находящихся в разных районах области, произрастает определенное количество единиц огурцов. Эту продукцию требуется доставить в n магазинов. В каждую из этих точек продажи необходимо доставить определенное количество огурцов. Стоимость перевозки единицы продукции с каждого дачного участка в каждый пункт продажи известна. Требуется так распределить поставки огурцов, чтобы общая стоимость перевозок была бы минимальной.

Входные данные

В первой строке даны 2 целых числа: 2 ≤ m ≤ 10 - количество огородов и 2 ≤ n ≤ 10 - количество магазинов, во второй строчке записаны m целых чисел 0 ≤ ai ≤ 1000 - количества огурцов на каждом из огородов, в третьей строчке n целых чисел 0 ≤ bj ≤ 1000 - количества огурцов, которые нужно доставить в каждый из магазинов, далее идёт таблица из m сток и n столбцов, на пересечении i-ой строки и j-ого столбца находится целое число 0 ≤ cij ≤ 1000 - стоимость перевозки (тариф) единицы продукции от i-го огорода в j-й магазин.

Выходные данные

В строке вывода нужно напечатать единственное целое число, равное минимальной общей стоимости всех перевозок.

Пример

Входные данные
3 5
15 25 20
20 12 5 8 15
1 0 3 4 2
5 1 2 3 3
4 8 1 4 3
Выходные данные
121

Примечание

С первого огорода в первый магазин везём 15 кг огурцов, со второго огорода во второй магазин - 12 кг огурцов, со второго огорода в четвёртый магазин - 8 кг огурцов, с третьего огорода в первый магазин - 5 кг огурцов, со второго в пятый - 5 кг, с третьего огорода в третий магазин - тоже 5 кг, и оставшиеся 10 кг везём с третьего огорода в пятый магазин. Общая стоимость перевозок 1·15 + 1·12 + 3·8 + 3·5 + 4·5 + 1·5 + 3·10 = 121

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований и сборов / Школьные олимпиады и курсы Вологодской области / Разные соревнования / VML Open Code Cup (November 2017) /
1808. 4 - Квадратное уравнение 1809.
Учебные курсы / Исследование операций / Линейное программирование /
2013. 04 - Транспортная задача 1809.
 
время генерации 0.093 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.