Description

Ringo is attending a carnival event held in Singapore. He has some tickets in his pocket, and these tickets can be used at the game booths in the carnival. Suppose there are $n$ colors of tickets. Each ticket is painted in exactly one color and has a non-negative integer printed on it. Different tickets may have the same number. According to the carnival rules, $n$ is guaranteed to be even.

Ringo has $m$ tickets of each color, so he has a total of $n \cdot m$ tickets. For the $j$-th ticket of color $i$, the printed number is $x[i][j]$ ($0 \le i \le n-1$ and $0 \le j \le m-1$).

A ticket game consists of $k$ rounds, numbered from $0$ to $k-1$. Each round works as follows:

• First, Ringo selects one ticket from each color, forming a set of $n$ tickets.
• Then, the game host writes down the numbers on the tickets in this set: $a[0],a[1],\ldots,a[n-1]$. The order of these $n$ integers does not matter.
• Next, the host draws a special card from a lucky draw box, which has an integer $b$ printed on it.
• For each ticket number $a[i](0\le i \le n-1)$ in the set, the host computes the absolute value of the difference between $a[i]$ and $b$. Let $S$ be the sum of these $n$ absolute differences.
• The value $S$ is the reward Ringo gets in this round.
• After the round ends, all tickets in the set are discarded and will not be used in future rounds.

After the $k$ rounds are finished, Ringo discards all remaining tickets in his pocket.

After careful observation, Ringo discovers that the ticket game is rigged. In fact, there is a printer inside the lucky draw box. In each round, the host first finds an integer $b$ that minimizes the reward of the current round, and then prints that number on the special card that he draws.

Knowing this, Ringo wants to design the ticket allocation plan for each round so that the total reward over the $k$ rounds is maximized.

Implementation details

You need to implement the following function:

long long find_maximum(int k,std::vector<std::vector<int>> x)

• $k$: the number of rounds.
• $x$: an $n \times m$ array recording the numbers on the tickets. For each color, the tickets are sorted in non-decreasing order of the numbers above.
• This function will be called only once.
• This function should call the function allocate_tickets exactly once (see below) to describe the allocation plan of tickets across the $k$ rounds, where each round corresponds to one set of tickets. The allocation plan should maximize the total reward.
• This function must return the maximum possible total reward.

The function allocate_tickets is defined as follows:

void allocate_tickets(std::vector<std::vector<int>> s)

• $s$: an $n \times m$ array. If the $j$-th ticket of color $i$ is assigned to round $r$, then $s[i][j]$ should be $r$; if it is not used, it should be $-1$.
• For each $0 \le i \le n-1$, in $s[i][0],s[i][1],\ldots,s[i][m-1]$, each value $0,1,\ldots,k-1$ must appear exactly once, and all other elements should be $-1$.
• If there are multiple optimal allocation plans that achieve the maximum reward, you may output any one of them.

Hint

Sample explanation

Example 1

Consider the following function call:

find_maximum(2, [[0, 2, 5],[1, 1, 3]])

This means:

• The game is played for $k=2$ rounds.
• The integers on the tickets of color $0$ are $0,2$ and $5$.
• The integers on the tickets of color $1$ are $1,1$ and $3$.

One optimal allocation plan is:

• In round $0$, Ringo chooses the $0$-th ticket of color $0$ (printed with $0$) and the $2$-nd ticket of color $1$ (printed with $3$). The minimum reward in this round is $3$. For example, the host can choose $b=1$: $|1-0| + |1-3| = 1+2 = 3$.
• In round $1$, Ringo chooses the $2$-nd ticket of color $0$ (printed with $5$) and the $1$-st ticket of color $1$ (printed with $1$). The minimum reward in this round is $4$. For example, the host can choose $b=3$: $|3-1|+|3-5|=2+2=4$.
• Therefore, the sum of rewards over the two rounds is $3+4=7$.

To output this allocation plan, find_maximum should call allocate_tickets as follows:

allocate_tickets([[0, -1, 1], [-1, 1, 0]])

Finally, find_maximum should return $7$.

Example 2

Consider the following function call:

find_maximum(1, [[5, 9], [1, 4], [3, 6], [2, 7]])

This means:

• The game is played for only one round.
• The numbers on tickets of color $0$ are $5$ and $9$.
• The numbers on tickets of color $1$ are $1$ and $4$.
• The numbers on tickets of color $2$ are $3$ and $6$.
• The numbers on tickets of color $3$ are $2$ and $7$.

One optimal allocation plan is:

• In round $0$, Ringo chooses the $1$-st ticket of color $0$ (printed with $9$), the $0$-th ticket of color $1$ (printed with $1$), the $0$-th ticket of color $2$ (printed with $3$), and the $1$-st ticket of color $3$ (printed with $7$). The minimum reward in this round is $12$. For example, the host can choose $b=3$: $|3-9| + |3-1| + |3-3| + |3-7| = 6 + 2 + 0 + 4 = 12$.

To output this allocation plan, find_maximum should call allocate_tickets as follows:

allocate_tickets([[-1, 0], [0, -1], [0, -1], [-1, 0]])

Finally, find_maximum should return $12$.

Constraints

• $2\le n\le 1500$ and $n$ is even.
• $1\le k\le m\le 1500$.
• $0 \le x[i][j] \le 10^9$ (for all $0 \le i \le n-1$ and $0 \le j \le m-1$).
• $x[i][j-1] \le x[i][j]$ (for all $0 \le i \le n-1$ and $0 \le j \le m-1$).

Subtasks

1. (11 points) $m=1$.
2. (16 points) $k=1$.
3. (14 points) $0 \le x[i][j] \le 1$ (for all $0 \le i \le n-1$ and $0 \le j \le m-1$).
4. (14 points) $k=m$.
5. (12 points) $n,m \le 80$.
6. (23 points) $n,m \le 300$.
7. (10 points) No additional constraints.

Sample grader program

The sample grader reads the input in the following format:

Line $1$: $n\ m\ k$
Line $2+i$ ($0 \le i \le n-1$): $x[i][0]\ x[i][1]\ \ldots \ x[i][m-1]$

The sample grader prints your output in the following format:

Line $1$: the return value of find_maximum
Line $2+i$ ($0 \le i \le n-1$): $s[i][0]\ s[i][1]\ \ldots\ s[i][m-1]$

Translated by ChatGPT 5