시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 43 | 30 | 23 | 69.697% |
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 \cdot m$ tickets. The ticket $j$ of the colour $i$ has the integer $x[i][j]$ printed on it ($0 \leq i \leq n-1$ and $0 \leq j \leq m-1$).
The prize game is played in $k$ rounds, numbered from $0$ to $k-1$. Each round is played in the following order:
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.
You should implement the following procedure:
int64 find_maximum(int k, int[][] x)
allocate_tickets
(see below), describing $k$ ticket sets, one for each round. The allocation should maximize the total value of the prizes.The procedure allocate_tickets
is defined as follows:
void allocate_tickets(int[][] s)
Consider the following call:
find_maximum(2, [[0, 2, 5],[1, 1, 3]])
This means that:
A possible allocation that gives the maximum total prize value is:
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$.
Consider the following call:
find_maximum(1, [[5, 9], [1, 4], [3, 6], [2, 7]])
This means that:
A possible allocation that gives the maximum total prize value is:
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$.
번호 | 점 | 제한 |
---|---|---|
1 | 11 | $m = 1$ |
2 | 16 | $k = 1$ |
3 | 14 | $0 \leq x[i][j] \leq 1$ (for all $0 \leq i \leq n-1$ and $0 \leq j \leq m - 1$) |
4 | 14 | $k = m$ |
5 | 12 | $n, m \leq 80$ |
6 | 23 | $n, m \leq 300$ |
7 | 10 | No additional constraints. |
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)