Модуль: Перебор перестановок


Задача

3 /4


Очередь в душ


Задача

Много студентов живут в общежитии. Общежитие — это большой мир веселых развлечений и возможностей, но у него есть свои минусы.
В общежитии всего один душ, а желающих принять душ утром, конечно, больше. Поэтому каждое утро перед душем общежития образуется очередь из пяти человек.
Как только душ открывается, первый человек из очереди заходит в душ. Спустя некоторое время, когда первый зашедший выходит из душа, следующий заходит в душ. Этот процесс продолжается, пока все в очереди не примут душ.

Душ — дело не быстрое, поэтому во время ожидания студенты общаются. В каждый момент времени студенты общаются парами: (2*i - 1)-й человек в очереди (на текущий момент) общается с (2*i)-м.
Рассмотрим этот процесс подробнее. Обозначим людей цифрами от 1 до 5. Пусть изначально очередь имеет вид 23154 (человек 2 стоит в начале очереди). Тогда перед открытием душа 2 общается с 3, 1 общается с 5, 4 ни с кем не общается. Затем 2 заходит в душ. Пока 2 принимает душ, 3 и 1 общаются, а также 5 и 4 общаются. Затем 3 заходит в душ. Пока 3 принимает душ, 1 и 5 общаются, 4 ни с кем не общается. Затем 1 заходит в душ, а пока он принимает душ, 5 и 4 общаются. Затем 5 заходит в душ, а затем 4 заходит в душ.

Известно, что если студенты i и j общаются, то радость студента i увеличивается на gi,j, а радость студента j увеличивается на gj,i.  Вам надо найти такой изначальный порядок студентов в очереди, чтобы суммарная радость всех студентов в итоге была максимальной. Стоит заметить, что некоторые студенты могут общаться несколько раз. В приведенном выше примере студенты 1 и 5 общаются пока ждут открытия душа, а также пока 3 принимает душ.

Сегодня возле душа выстроилась очередь ровно из 5 студентов. Найдите максимально возможную суммарную радость этих студентов.

Входные данные
Входные данные состоят из пяти строк, в каждой строке записано пять целых чисел разделенных пробелом: j-е число в i-й строке обозначает gi,j (0 ≤ gi,j≤ 105). Гарантируется, что gi,i = 0 для всех i.
Считайте, что студенты пронумерованы от 1 до 5.

Выходные данные
Выведите единственное целое число — максимально возможную суммарную радость студентов.
 
Примеры
Входные данныеВыходные данные
1 0 0 0 0 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
7 0 0 0 0
32
2 0 43 21 18 2
3 0 21 11 65
5 2 0 1 4
54 62 12 0 99
87 64 81 33 0
620

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6410
Python46
Комментарий учителя