Обратите внимание на необычное ограничение по памяти в этой задаче.
Сотрудники MDCS (Microsoft Development Center Serbia, сербского центра разработок Майкрософта) любят вечеринки. Обычно они ходят в ночные клубы в пятницу и субботу.
Всего в MDCS работает N людей, а в городе всего есть N клубов. К сожалению, если в ночном клубе будет больше одного сотрудника Майкрософта, то уровень крутизны этой вечеринки возрастает до небес, и вечеринка заканчивается, так что владельцы клуба никогда не позволяют более, чем одному сотруднику Майкрософта войти в их клуб в течение недели (так, на всякий случай).
Вы организуете ночную жизнь сотрудников Майкрософта и у Вас есть статистика о том, насколько каждому сотруднику нравятся вечеринки в пятницу и субботу, для всех клубов.
Вам надо распределить людей по клубам, максимизируя общую сумму их довольства (они настолько довольны, насколько им нравится выбранный клуб), при этом половина людей должна пойти клубиться в пятницу, а другая половина — в субботу.
Примечание
Распределение людей по клубам в примере:
Пятница: 1-й человек идет в 4-й клуб (4 единицы довольства), а 4-й человек идет в 1-й клуб (4 единицы довольства).
Суббота: 2-й человек идет в 3-й клуб (81 единица довольства), а 3-й человек идет во 2-й клуб (78 единиц довольства).
4 + 4 + 81 + 78 = 167.