| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 1 | 0 | 0 | 0.000% |
Дана таблица $a$, состоящая из $r$ строк и $c$ столбцов, в которой записаны в произвольном порядке все различные числа от $1$ до $r \cdot c$. Элементы этой таблицы переносятся в изначально пустой массив $b$.
Пока таблица непустая, над ней выполняется одно из двух действий:
Порядок действий требуется выбирать таким, чтобы количество инверсий в полученном массиве после применения всех операций было минимальным.
Инверсией называется такая пара индексов элементов массива $1 \le i < j \le r\cdot c$, что $b_i > b_j$.
Первая строка содержит два целых числа $r$ и $c$ ($r \le c$, $1 \le r \cdot c \le 2\,000\,000$) --- количество строк и столбцов в таблице соответственно.
В следующих $r$ строках содержится описание таблицы $a$. В $i$-й из них содержится $c$ целых чисел $a_{i1}$, $\ldots$, $a_{ic}$ ($1 \le a_{ij} \le r \cdot c$) --- элементы матрицы $a$.
Гарантируется, что все числа в таблице $a$ различны.
Выведите одно число --- минимально возможное количество инверсий в массиве $b$ после применения всех операций.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 15 | $r + c \le 14$ |
| 2 | 18 | $ r \cdot c \le 500 $ |
| 3 | 5 | Все строки и столбцы отсортированы в возрастающем порядке и $ r \cdot c \le 250\,000 $ |
| 4 | 7 | $r = 1$, $ r \cdot c \le 250\,000 $ |
| 5 | 6 | $r \le 2$, $ r \cdot c \le 250\,000 $ |
| 6 | 2 | $r \le 20 $, $ r \cdot c \le 250\,000 $ |
| 7 | 10 | $r,\ c \le 100$ |
| 8 | 2 | $r \cdot c \le 10\,000$ |
| 9 | 1 | $r \le 100$, $c \le 1000$ |
| 10 | 1 | $r \le 100$, $c \le 2500$ |
| 11 | 1 | $r \le 100$, $c \le 5000$ |
| 12 | 1 | $r \le 100$, $c \le 7500$ |
| 13 | 1 | $r \le 100$, $c \le 10\,000$ |
| 14 | 4 | $r \le 100$, $c \le 15\,000$ |
| 15 | 2 | $r \le 100$, $c \le 20\,000$ |
| 16 | 3 | $r,\ c \le 200$ |
| 17 | 3 | $r,\ c \le 400$ |
| 18 | 4 | $r,\ c \le 600$ |
| 19 | 1 | $r,\ c \le 800$ |
| 20 | 1 | $r,\ c \le 1000$ |
| 21 | 1 | $r,\ c \le 1200$ |
| 22 | 1 | $r,\ c \le 1400$ |
| 23 | 1 | $r \cdot c \le 100\,000$ |
| 24 | 1 | $r \cdot c \le 250\,000$ |
| 25 | 4 | $r \cdot c \le 500\,000$ |
| 26 | 1 | $r \cdot c \le 750\,000$ |
| 27 | 1 | $r \cdot c \le 1\,000\,000$ |
| 28 | 1 | $r \cdot c \le 1\,500\,000$ |
| 29 | 1 |
2 3 3 4 1 5 6 2
6
2 3 2 3 4 1 6 5
2
В первом примере минимальное число инверсий достигается при двукратном удалении первой строки. В результате массив $b$ будет равен $[3, 4, 1, 5, 6, 2]$. Такой массив содержит $6$ инверсий.
Во втором примере для достижения минимального числа инверсий можно сначала удалить первый столбец, а потом два раза удалить первую строку. В результате массив $b$ будет равен $[2, 1, 3, 4, 6, 5]$. Такой массив содержит $2$ инверсии.