Carnival Tickets (tickets)

Ringo is at a carnival in Singapore. He has some prize tickets in his bag, which he would like to use at the prize game stall. Each ticket comes in one of n colours and has a non-negative integer printed on it. The integers printed on different tickets might be the same. Due to a quirk in the carnival rules, n is guaranteed to be even.

Ringo has m tickets of each colour in his bag, that is a total of n · m tickets. The ticket j of the colour i has the integer x[i][j] printed on it (0 ≤ i ≤ n − 1 and 0 ≤ j ≤ m − 1).

The prize game is played in k rounds, numbered from 0 to k − 1. Each round is played in the following order:

• From his bag, Ringo selects a set of n tickets, one ticket from each colour. He then gives the set to the game master.
• The game master notes down the integers a[0], a[1] ... a[n − 1] printed on the tickets of the set. The order of these n integers is not important.
• The game master pulls out a special card from a lucky draw box and notes down the integer b printed on that card.
• The game master calculates the absolute differences between a[i] and b for each i from 0 to n − 1. Let S be the sum of these absolute differences.
• For this round, the game master gives Ringo a prize with a value equal to S.
• The tickets in the set are discarded and cannot be used in future rounds.

The remaining tickets in Ringo's bag after k rounds of the game are discarded.

By watching closely, Ringo realized that the prize game is rigged! There is actually a printer inside the lucky draw box. In each round, the game master finds an integer b that minimizes the value of the prize of that round. The value chosen by the game master is printed on the special card for that round.

Having all this information, Ringo would like to allocate tickets to the rounds of the game. That is, he wants to select the ticket set to use in each round in order to maximize the total value of the prizes.

Implementation details

You should implement the following procedure:

int64 find_maximum(int k, int[][] x)

• k: the number of rounds.
• x: an n × m array describing the integers on each ticket. Tickets of each color are sorted in non-decreasing order of their integers.
• This procedure is called exactly once.
• This procedure should make exactly one call to allocate_tickets (see below), describing k ticket sets, one for each round. The allocation should maximize the total value of the prizes.
• This procedure should return the maximum total value of the prizes.

The procedure allocate_tickets is defined as follows:

void allocate_tickets(int[][] s)

• s: an n × m array. The value of s[i][j] should be r if the ticket j of the colour i is used in the set of round r of the game, or −1 if it is not used at all.
• For each 0 ≤ i ≤ n − 1, among s[i][0], s[i][1], . . . , s[i][m − 1] each value 0, 1, 2, . . . , k − 1 must occur exactly once, and all other entries must be −1.
• If there are multiple allocations resulting in the maximum total prize value, it is allowed to report any of them.

Examples

Example 1

Consider the following call:

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

This means that:
* there are k = 2 rounds;
* the integers printed on the tickets of colour 0 are 0, 2 and 5, respectively;
* the integers printed on the tickets of colour 1 are 1, 1 and 3, respectively.

A possible allocation that gives the maximum total prize value is:

• In round 0, Ringo picks ticket 0 of colour 0 (with the integer 0) and ticket 2 of colour 1 (with the integer 3). The lowest possible value of the prize in this round is 3. E.g., the game master may choose b = 0: |0 − 0| + |3 − 0| = 0 + 3 = 3.
• In round 1, Ringo picks ticket 2 of colour 0 (with the integer 5) and ticket 1 of colour 1 (with the integer 1). The lowest possible value of the prize in this round is 4. E.g., the game master may choose b = 3: |5 − 3| + |1 − 3| = 2 + 2 = 4.
• Therefore, the total value of the prizes would be 3 + 4 = 7.

To report this allocation, the procedure find_maximum should make the following call to allocate_tickets:

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

Finally, the procedure find_maximum should return 7.

Example 2

Consider the following call:

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

This means that:
* there is only one round,
* the integers printed on the tickets of colour 0 are 5 and 9, respectively;
* the integers printed on the tickets of colour 1 are 1 and 4, respectively;
* the integers printed on the tickets of colour 2 are 3 and 6, respectively;
* the integers printed on the tickets of colour 3 are 2 and 7, respectively.

A possible allocation that gives the maximum total prize value is:

• In round 0, Ringo picks ticket 1 of colour 0 (with the integer 9), ticket 0 of colour 1 (with the integer 1), ticket 0 of colour 2 (with the integer 3), and ticket 1 of colour 3 (with the integer 7). The lowest possible value of the prize in this round is 12, when the game master chooses b = 3: |3 − 9| + |3 − 1| + |3 − 3| + |3 − 7| = 6 + 2 + 0 + 4 = 12.

To report this solution, the procedure find_maximum should make the following call to allocate_tickets:

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

Finally, the procedure 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 $1 \le j \le m - 1$)
• For each call to count_tastiness, the sum of tastiness values of all biscuits in the pantry does not exceed $10^{18}$.

Sample grader

The sample grader reads the input in the following format:

• line 1: n m k
• line 2 + i (0 ≤ i ≤ n − 1): x[i][0] x[i][1] ... x[i][m − 1]

The sample grader prints your answer in the following format:

• line 1: the return value of find_maximum
• line 2 + i (0 ≤ i ≤ n − 1): s[i][0] s[i][1] ... s[i][m − 1]

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Carnival Tickets)

(tickets)

Ringo is at a carnival in Singapore. He has some prize tickets in his bag, which he would like to use at the prize game stall. Each ticket comes in one of n colours and has a non-negative integer printed on it. The integers printed on different tickets might be the same. Due to a quirk in the carnival rules, n is guaranteed to be even.

Ringo has m tickets of each colour in his bag, that is a total of n · m tickets. The ticket j of the colour i has the integer x[i][j] printed on it (0 ≤ i ≤ n − 1 and 0 ≤ j ≤ m − 1).

The prize game is played in k rounds, numbered from 0 to k − 1. Each round is played in the following order:

• From his bag, Ringo selects a set of n tickets, one ticket from each colour. He then gives the set to the game master.
• The game master notes down the integers a[0], a[1] ... a[n − 1] printed on the tickets of the set. The order of these n integers is not important.
• The game master pulls out a special card from a lucky draw box and notes down the integer b printed on that card.
• The game master calculates the absolute differences between a[i] and b for each i from 0 to n − 1. Let S be the sum of these absolute differences.
• For this round, the game master gives Ringo a prize with a value equal to S.
• The tickets in the set are discarded and cannot be used in future rounds.

The remaining tickets in Ringo's bag after k rounds of the game are discarded.

By watching closely, Ringo realized that the prize game is rigged! There is actually a printer inside the lucky draw box. In each round, the game master finds an integer b that minimizes the value of the prize of that round. The value chosen by the game master is printed on the special card for that round.

Having all this information, Ringo would like to allocate tickets to the rounds of the game. That is, he wants to select the ticket set to use in each round in order to maximize the total value of the prizes.

Implementation details

You should implement the following procedure:

int64 find_maximum(int k, int[][] x)

• k: the number of rounds.
• x: an n × m array describing the integers on each ticket. Tickets of each color are sorted in non-decreasing order of their integers.
• This procedure is called exactly once.
• This procedure should make exactly one call to allocate_tickets (see below), describing k ticket sets, one for each round. The allocation should maximize the total value of the prizes.
• This procedure should return the maximum total value of the prizes.

The procedure allocate_tickets is defined as follows:

void allocate_tickets(int[][] s)

• s: an n × m array. The value of s[i][j] should be r if the ticket j of the colour i is used in the set of round r of the game, or −1 if it is not used at all.
• For each 0 ≤ i ≤ n − 1, among s[i][0], s[i][1], . . . , s[i][m − 1] each value 0, 1, 2, . . . , k − 1 must occur exactly once, and all other entries must be −1.
• If there are multiple allocations resulting in the maximum total prize value, it is allowed to report any of them.

Examples

Example 1

Consider the following call:

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

This means that:
* there are k = 2 rounds;
* the integers printed on the tickets of colour 0 are 0, 2 and 5, respectively;
* the integers printed on the tickets of colour 1 are 1, 1 and 3, respectively.

A possible allocation that gives the maximum total prize value is:

• In round 0, Ringo picks ticket 0 of colour 0 (with the integer 0) and ticket 2 of colour 1 (with the integer 3). The lowest possible value of the prize in this round is 3. E.g., the game master may choose b = 0: |0 − 0| + |3 − 0| = 0 + 3 = 3.
• In round 1, Ringo picks ticket 2 of colour 0 (with the integer 5) and ticket 1 of colour 1 (with the integer 1). The lowest possible value of the prize in this round is 4. E.g., the game master may choose b = 3: |5 − 3| + |1 − 3| = 2 + 2 = 4.
• Therefore, the total value of the prizes would be 3 + 4 = 7.

To report this allocation, the procedure find_maximum should make the following call to allocate_tickets:

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

Finally, the procedure find_maximum should return 7.

Example 2

Consider the following call:

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

This means that:
* there is only one round,
* the integers printed on the tickets of colour 0 are 5 and 9, respectively;
* the integers printed on the tickets of colour 1 are 1 and 4, respectively;
* the integers printed on the tickets of colour 2 are 3 and 6, respectively;
* the integers printed on the tickets of colour 3 are 2 and 7, respectively.

A possible allocation that gives the maximum total prize value is:

• In round 0, Ringo picks ticket 1 of colour 0 (with the integer 9), ticket 0 of colour 1 (with the integer 1), ticket 0 of colour 2 (with the integer 3), and ticket 1 of colour 3 (with the integer 7). The lowest possible value of the prize in this round is 12, when the game master chooses b = 3: |3 − 9| + |3 − 1| + |3 − 3| + |3 − 7| = 6 + 2 + 0 + 4 = 12.

To report this solution, the procedure find_maximum should make the following call to allocate_tickets:

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

Finally, the procedure 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 $1 \le j \le m - 1$)
• For each call to count_tastiness, the sum of tastiness values of all biscuits in the pantry does not exceed $10^{18}$.

Sample grader

The sample grader reads the input in the following format:

• line 1: n m k
• line 2 + i (0 ≤ i ≤ n − 1): x[i][0] x[i][1] ... x[i][m − 1]

The sample grader prints your answer in the following format:

• line 1: the return value of find_maximum
• line 2 + i (0 ≤ i ≤ n − 1): s[i][0] s[i][1] ... s[i][m − 1]

Execution limits

Your solution will have 2.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "tickets.h"
#include <vector>

long long find_maximum(int k, std::vector<std::vector<int>> x) {
    int n = x.size();
    int m = x[0].size();
    std::vector<std::vector<int>> answer;
    for (int i = 0; i < n; i++) {
        std::vector<int> row(m);
        for (int j = 0; j < m; j++) {
            if (j < k) {
                row[j] = j;
            } else {
                row[j] = -1;
            }
        }
        answer.push_back(row);
    }
    allocate_tickets(answer);
    return 1;
}

参考函数签名

#include "tickets.h"
#include <vector>

long long find_maximum(int k, std::vector<std::vector<int>> x) {
    int n = x.size();
    int m = x[0].size();
    std::vector<std::vector<int>> answer;
    for (int i = 0; i < n; i++) {
        std::vector<int> row(m);
        for (int j = 0; j < m; j++) {
            if (j < k) {
                row[j] = j;
            } else {
                row[j] = -1;
            }
        }
        answer.push_back(row);
    }
    allocate_tickets(answer);
    return 1;
}

请在 submission.cpp 中实现该函数（可 #include "problem.h" 获取题目提供的声明）。判题时你的代码会与题目提供的 grader 一起编译链接。

本题是函数题，由 grader 调用你实现的函数。

由 grader 打印判定结果，无需自行读写 stdin/stdout。

include "tickets.h"

include <vector>

long long find_maximum(int k, std::vector<std::vector\<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector\<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row(m);
for (int j = 0; j < m; j++) {
if (j < k) {
row[j] = j;
} else {
row[j] = -1;
}
}
answer.push_back(row);
}
allocate_tickets(answer);
return 1;
}