Ограничение времени | 3 секунды |
Ограничение памяти | 256 Мб |
Ввод | стандартный ввод |
Вывод | стандартный вывод |
В этой задаче на проверку необходимо сдать программу, которая будет решать поставленную задачу.
Всем известно, что последовательный доступ к данным намного быстрее произвольного. Данные, хранящиеся на диске, разделены на блоков одинакового размера. Блоки данных занумерованы числами от до и размещены на позициях на диске, которые также занумерованы числами от до . Единственная разрешенная операция — обмен блоков данных на двух позициях. Для каждой пары позиций задано время, необходимое для обмена блоков данных, расположенных на этих позициях. Для оптимизации производительности чтения данных на каждом из дисков сервера необходимо переупорядочить блоки данных таким образом, чтобы их номера образовывали возрастающую последовательность.
В первой строке вводится число ( ) — количество дисков на сервере.
Далее следует описаний дисков.
В первой строке каждого описания содержится число ( ) — количество позиций для хранения блоков данных на этом диске.
Во второй строке задана перестановка из чисел от до — номера блоков, в том порядке, в котором они размещены на позициях.
В следующих строках содержится матрица , описывающая время обмена блоков данных. Целое число , где — номер строки, а — номер столбца при нумерации с единицы, задает время обмена блоков данных, расположенных на позициях и . При этом . Числа не превосходят 1000.
Для каждого из дисков выведите время, необходимое для упорядочивания блоков данных.
Ввод | Вывод |
---|---|
3 2 2 1 0 1 1 0 3 1 2 3 0 9 4 9 0 6 4 6 0 3 2 3 1 0 1 10 1 0 6 10 6 0 | 1 0 7 |
Оценка за эту задачу — 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).
Каждое верно определенное время оценивается в 5 баллов.