Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1175. Матрица
Задача о назначенияхОлимпиадные задачи на русском языке
| 20/12/2008 | Занятие 12 (C) |
| 20/07/2020 | Летние сборы - 10 (C) |
| 29/11/2021 | Дискретная оптимизация - 6 (проводит BOGAT) (A) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дана матрица размером `N\ times\ N`. Необходимо найти такое подмножество из `N` элементов матрицы, что
(a) в каждом столбце и каждом столбце находится не более одного выбранного элемента
(б) сумма выбранных элементов является наибольшей из возможных.
В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 100`). Далее следует `N` строк,
содержащих по `N` целых чисел от 1 до 1000 – элементы матрицы.
Вывести в первой строке максимальную сумму. Во второй строке вывести `N` чисел – номера столбцов
с выбранными элементами для каждой строки матрицы. Если существует несколько решений с
максимальной суммой, то вывести любое из них.
Пример ввода
3 7 5 1 3 4 3 2 3 1
Пример вывода
13 1 3 2
