Общежитие ОшГУ


Отправить решение Решать в редакторе

Сложность: 75%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В новом общежитии Ошского государственного университета n свободных мест, и ровно n первокурсников ждут заселения. Студенты приехали из разных уголков страны — из Баткена, Нарына, Таласа, Каракола, — а места находятся в разных корпусах и на разных этажах.

Комендант Гульнара эже провела опрос и для каждого студента i и каждого места j оценила неудобство c[i][j]: сколько минут в день студент будет тратить на дорогу до своего факультета, с поправкой на этаж, соседей и пожелания. Некоторые сочетания недопустимы (например, места в женском блоке для юношей); они отмечены числом -1.

Нужно поселить всех студентов, каждого на отдельное место, так, чтобы суммарное неудобство было минимальным. Выведите это минимальное суммарное неудобство или -1, если поселить всех по правилам невозможно.

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

В первой строке — целое число n (1 ≤ n ≤ 500).

В каждой из следующих n строк — по n целых чисел: j-е число i-й строки равно c[i][j] (0 ≤ c[i][j] ≤ 10⁶ или c[i][j] = −1).

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

Выведите одно целое число — минимальное суммарное неудобство или -1.

Пример 1

Вход:

3
4 1 3
2 0 5
3 2 -1

Выход:

6

Пример 2

Вход:

2
5 -1
7 -1

Выход:

-1

Пояснение

В первом примере выгодно поселить первого студента на место 3, второго — на место 2, третьего — на место 1: 3 + 0 + 3 = 6. Во втором примере оба студента могут жить только на месте 1.

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 15 n ≤ 12
2 25 n ≤ 100
3 60 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.


Комментарии

Еще нет ни одного комментария.