| Codeforces Global Round 16 |
|---|
| Закончено |
Это сложная версия задачи. Единственное различие состоит в том, что в этой версии $$$1 \le n \le 300$$$.
В кинотеатре места могут быть представлены как таблица из $$$n$$$ рядов и $$$m$$$ столбцов. Ряды нумеруются целыми числами от $$$1$$$ до $$$n$$$. Места в каждом ряду нумеруются последовательными целыми числами слева направо: в $$$k$$$-м ряду от $$$m (k - 1) + 1$$$ до $$$m k$$$ для всех рядов $$$1 \le k \le n$$$.
| $$$1$$$ | $$$2$$$ | $$$\cdots$$$ | $$$m - 1$$$ | $$$m$$$ |
| $$$m + 1$$$ | $$$m + 2$$$ | $$$\cdots$$$ | $$$2 m - 1$$$ | $$$2 m$$$ |
| $$$2m + 1$$$ | $$$2m + 2$$$ | $$$\cdots$$$ | $$$3 m - 1$$$ | $$$3 m$$$ |
| $$$\vdots$$$ | $$$\vdots$$$ | $$$\ddots$$$ | $$$\vdots$$$ | $$$\vdots$$$ |
| $$$m (n - 1) + 1$$$ | $$$m (n - 1) + 2$$$ | $$$\cdots$$$ | $$$n m - 1$$$ | $$$n m$$$ |
Есть $$$nm$$$ людей, которые хотят прийти в кинотеатр, чтобы посмотреть новый фильм. Они пронумерованы целыми числами от $$$1$$$ до $$$nm$$$. Вы должны задать ровно одно место для каждого человека.
Известно, что в этом кинотеатре чем меньше номер места, тем лучше виден экран. У $$$i$$$-го человека уровень зрения $$$a_i$$$. Обозначим за $$$s_i$$$ номер места $$$i$$$-го человека. Необходимо выдать место лучше тем, у кого зрение хуже, то есть для любых двух людей $$$i$$$, $$$j$$$ таких, что $$$a_i < a_j$$$, должно выполняться условие $$$s_i < s_j$$$.
После того, как вы определите места всем людям, они начнут их занимать. В порядке от $$$1$$$ до $$$nm$$$ каждый человек входит в зал и садится на своё место. Чтобы сесть, человек подходит к своему ряду и начинает двигаться от первого места в ряду к своему слева направо. Во время того, как человек будет занимать свое место, какие-то места будут свободны, какие-то будут заняты теми людьми, которые уже вошли в зал. Неудобство человека равно количеству занятых мест, мимо которых он прошёл, пока занимал своё место.
Рассмотрим пример: $$$m = 5$$$, человеку определено место $$$4$$$ в первом ряду, причём места $$$1$$$, $$$3$$$, $$$5$$$ в первом ряду уже заняты, а места $$$2$$$ и $$$4$$$ свободны. Неудобство этого человека будет равно $$$2$$$, потому что он пройдет мимо двух занятых мест: $$$1$$$ и $$$3$$$.
Найдите минимальное общее неудобство (сумму неудобств всех людей), которое можно получить, задав места для всех людей (при этом все условия должны быть выполнены).
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 300$$$) — количество рядов и мест в каждом ряду кинотеатра соответственно.
Следующая строка содержит $$$n \cdot m$$$ целых чисел $$$a_1, a_2, \ldots, a_{n \cdot m}$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — уровень зрения $$$i$$$-го человека.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превышает $$$10^5$$$.
Для каждого набора выходных данных выведите единственное целое число — минимальное общее неудобство, которое можно получить.
7 1 2 1 2 3 2 1 1 2 2 3 3 3 3 3 4 4 1 1 1 1 1 2 2 2 1 1 2 1 4 2 50 50 50 50 3 50 50 50 4 2 6 6 6 6 2 2 9 6 2 9 1 3 3 3 3 3 1 1 3 1 3 1 1 3 3 1 1 3
1 0 4 0 0 0 1
В первом наборе входных данных существует единственный способ рассадить людей: первого человека посадить на первое место, а второго — на второе. Тогда суммарное неудобство будет равно $$$1$$$.
Во втором наборе входных данных оптимальная рассадка выглядит следующим образом:
В третьем наборе входных данных оптимальная рассадка выглядит следующим образом:
Число в клетке обозначает индекс человека, занимающего это место.
