#3366. 「IOI2020」嘉年华奖券

内存限制:1024 MiB 时间限制:2000 ms 题目类型:交互
上传者: EntropyIncreaser

题目描述

注意:在 LibreOJ 上,由于语言限制,目前只支持以下语言的提交:

  • C++ 11
  • C++ 11 (Clang)
  • C++ 11 (NOI)
  • C++ 17
  • C++ 17 (Clang)

Ringo 正在参加在新加坡举办的一个嘉年华活动。他的口袋里装有一些奖券,这些奖券可以在嘉年华的游戏展位使用。假设共有 n 种颜色的奖券,每张奖券涂上了其中的一种颜色并且印上了一个非负整数。不同奖券上的数字可能相同。依据嘉年华活动的规则要求, n 保证是偶数。

Ringo 每种颜色的奖券有 m 张,也就是说他共有 n\cdot m 张奖券。其中,第 i 种颜色对应的第 j 张奖券上印的数字为 x_{i,j} 0\le i\le n-1 0\le j\le m - 1 )。

一次奖券游戏要进行 k 轮,轮次的序号从 0 k-1 。每一轮按照下面的方式进行:

  • 首先,Ringo 从每种颜色的奖券中各选出一张奖券,形成一个 n 张奖券的集合

  • 随后,游戏负责人记录下这个集合中奖券上的数字 a_0, a_1, \dots, a_{n-1} 。不需要考虑这 n 个整数的顺序。

  • 接下来,游戏负责人从一个幸运抽奖箱中抽取一张特殊卡片,上面印有整数 b

  • 对于上述集合中每一个奖券上的数字 a_i(0\le i \le n-1) ,游戏负责人会计算 a_i b 的差的绝对值。让 S 代表这 n 个差的绝对值之和。

  • 所得到的数字 S 就是 Ringo 本轮能够获得的奖励数额。

  • 一轮游戏结束后,本轮集合中的奖券全部被丢弃,不会在未来的轮次所使用。

k 轮游戏结束后,Ringo 会丢弃口袋中的所有奖券。

通过仔细观察,Ringo 发现这个奖券游戏被操控了!实际上,幸运抽奖箱里面内置了一台打印机。在每一轮,游戏负责人首先找到一个能够最小化当前轮次游戏奖励的整数 b ,然后将该数字打印在他所抽取的特殊卡片上。

知道了这些信息之后,Ringo 想要设计每轮游戏中的奖券分配方案,使得 k 轮游戏中获得的总体奖励数额之和最大。

实现细节

你需要实现下面这个函数:

long long find_maximum(int k, std::vector<std::vector<int>> x)
  • k :游戏的轮数。

  • x :一个 n\times m 的数组,记录了奖券上的数字。每种颜色的奖券按照上面的数字非递减顺序排序。

  • 这个函数只会被调用一次。

  • 这个函数应该只调用一次函数 allocate_tickets(参见下面的内容),它描述了 k 轮游戏中的奖券分配方案,每一轮对应一个奖券集合。奖券的分配方案应该使得所获奖励数额之和达到最大。

  • 这个函数需要返回能够获得的最大的奖励数额之和。

函数 allocate_tickets 按照如下的方式进行定义:

void allocate_tickets(std::vector<std::vector<int>> s)
  • s :一个 n\times m 的数组。如果第 i 种颜色的第 j 张奖券如果被分配到了第 r 轮游戏,那么 s_{i,j} 的值应该为 r ;如果未被使用,应该为 -1

  • 对于 0\le i\le n-1 ,在 s_{i,0}, s_{i,1}, \dots, s_{i,m-1} 中,每个值 0, 1, \dots, k - 1 必须只出现一次,而其他元素应该为 -1

  • 如果存在多种奖券分配方案能够达到最优的奖励数值,可以给出其中任何一种最优方案。

评测程序示例

评测程序示例按照下面的格式读入数据:

  • 1 行: n\ m\ k
  • 2 + i 行( 0\le i\le n-1 ): x_{i, 0}\ x_{i,1}\ \dots\ x_{i,m-1}

评测程序示例按照下面的格式打印你的答案:

  • 1 行:find_maximum 的返回值
  • 2 + i 行( 0\le i\le n-1 ): s_{i, 0}\ s_{i,1}\ \dots\ s_{i,m-1}

样例

样例输入 1

2 3 2
0 2 5
1 1 3

样例输出 1

7
0 -1 1
-1 1 0

样例解释 1

考虑下面的函数调用:

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

这意味着:

  • 游戏共进行 k=2 轮;
  • 0 种颜色奖券上的整数数字分别是 0, 2 5
  • 1 种颜色奖券上的整数数字分别是 1, 1 3

一种能够获得最优奖励数值的分配方案是:

  • 在第 0 轮,Ringo 选择第 0 种颜色的第 0 张奖券(印有整数 0 )和第 1 种颜色的第 2 张奖券(印有整数 3 )。本轮获得的最小奖励数额是 3 。例如,游戏负责人可以选择 b=1 |1-0| + |1-3| = 1+2 = 3

  • 在第 1 轮,Ringo 选择第 0 种颜色的第 2 张奖券(印有整数 5 )和第 1 种颜色的第 1 张奖券(印有整数 1 )。本轮能够获得的最小奖励是 4 。例如,游戏负责人可以选择 b=3 |3-1|+|3-5|=2+2=4

  • 因此,本次游戏两轮的奖励之和为 3+4=7

为了给出这个分配方案,函数 find_maximum 应该按照如下方式调用 allocate_tickets

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

最终,函数 find_maximum 应该返回数字 7

样例输入 2

4 2 1
5 9
1 4
3 6
2 7

样例输出 2

12
-1 0
0 -1
0 -1
-1 0

样例解释 2

考虑下面的函数调用:

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

这意味着:

  • 游戏只进行一轮;
  • 0 种颜色奖券上的数字分别是 5 9
  • 1 种颜色奖券上的数字分别是 1 4
  • 2 种颜色奖券上的数字分别是 3 6
  • 3 种颜色奖券上的数字分别是 2 7

一种能够获得最优奖励的分配方案是:

  • 在第 0 轮,Ringo 选择第 0 种颜色的第 1 张奖券(印有整数 9 ) ,第 1 种颜色的第 0 张奖券(印有整数 1 ),第 2 种颜色的第 0 张奖券(印有整数 3 ),第 3 种颜色的第 1 张奖券(印有整数 7 )。本轮能够获得的最小奖励是 12 。例如,游戏负责人可以选择 b=3

|3-9| + |3-1| + |3-3| + |3-7| = 6 + 2 + 0 + 4 = 12

为了给出这个分配方案,函数 find_maximum 应该按照如下方式调用 allocate_tickets

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

最终,函数 find_maximum 应该返回数字 12

数据范围与提示

对于 100\% 的数据,保证:

  • 2\le n\le 1500 n 为偶数
  • 1\le k\le m\le 1500
  • 0\le x_{i,j}\le 10^9 (对于所有的 0\le i\le n-1 0\le j\le m-1
  • x_{i,j-1}\le x_{i,j} (对于所有的 0\le i\le n-1 1\le j\le m-1
子任务 附加限制 分值
1 m=1 11
2 k=1 16
3 0\le x_{i,j}\le 1 (对于所有的 0\le i\le n-1 0\le j\le m-1 14
4 k=m 14
5 n,m\le 80 12
6 n,m\le 300 23
7 没有其他限制 10