NZIC 2026 Round 1（新西兰信息学竞赛 2026 第三轮）

D.Birthday Cake（生日蛋糕）

输入： 标准输入（stdin） 输出： 标准输出（stdout） 内存限制： 256 MB 时间限制： 1.5 秒

• problem statement
• files
• submit
• submissions

---

题目描述

今天是你朋友的生日，你决定给他烤一个蛋糕。

但是，这是你第一次烘焙任何东西，结果发现自己并不擅长这件事。

由于你过于天真和自信，你决定既不按照任何食谱操作，也不测量任何原料。

结果就是，你现在完全不知道自己到底做出了多少蛋糕，也不知道这些蛋糕够不够朋友生日聚会上的所有客人吃。

更糟糕的是，你不仅烘焙水平不高，而且动作还特别慢。你已经快要赶不上朋友的生日聚会了，因此没有时间准确测量自己做出的蛋糕体积。

问题还在于，你做出来的蛋糕并不是一个厚度均匀、形状规整的长方体，而是一团厚薄不均的东西。

如果想准确计算它的体积，唯一的方法就是测量蛋糕每一个位置的厚度，但你显然没有时间这么做。

---

于是，你决定把蛋糕划分成：

$$N$$

行和：

$$M$$

列。

每一行和每一列的宽度都是 1 厘米，因此整个蛋糕被划分成：

$$N\times M$$

个面积为 1 平方厘米的方格。

然后，你分别记录：

• 每一行中最厚的格子的厚度；
• 每一列中最厚的格子的厚度。

这些厚度都以厘米为单位。

你可以假设：

• 每一个格子内部的厚度是均匀的；
• 每个格子的厚度都是一个非零整数。

接下来，你希望根据这些测量结果，计算蛋糕总体积的：

• 最小可能值；
• 最大可能值。

体积单位是立方厘米。

不过，由于时间已经非常紧张，你必须编写一个程序来完成这个计算。

---

输入格式

第一行包含两个用空格分隔的整数：

N M

分别表示蛋糕的行数和列数。

第二行包含 (N) 个用空格分隔的整数：

表示每一行中所有格子的最大厚度。

第三行包含 (M) 个用空格分隔的整数：

表示每一列中所有格子的最大厚度。

---

输出格式

输出一行两个用空格分隔的整数：

minimum maximum

其中：

• 第一个整数表示与测量结果一致的蛋糕的最小可能体积；
• 第二个整数表示与测量结果一致的蛋糕的最大可能体积。

---

数据范围

$$1\le N,M\le200000$$

所有厚度值都满足：

$$1\le \text{thickness}\le10^6$$

保证至少存在一种蛋糕的厚度分布，与给出的行最大值和列最大值完全一致。

---

子任务

• 子任务 1（+16%）：

所有行和所有列的最大厚度都相同。

• 子任务 2（+18%）：

$$N=M=2$$

• 子任务 3（+26%）：

$$N,M\le2000$$

• 子任务 4（+40%）：

没有额外限制。

---

评分方式

对于每一个测试点：

• 如果你的输出格式不符合要求，或者两个整数都错误，则得分为 0%；
• 如果两个整数中只有一个正确，则得分为 50%；
• 如果两个整数都正确，则得分为 100%。

某个子任务的得分，是该子任务所有测试点得分中的最小值。

注意：

即使你只打算拿某个子任务的 50% 分数，也仍然必须输出两个整数，输出格式才算正确。

---

注意事项

如果你使用 Python，并且程序超过时间限制，可以尝试在提交时选择：

Python 3.11 (PyPy 7.3.19)

通常这样会让程序运行得更快。

如果你使用的是对整数类型比较敏感的语言，例如：

• C++
• Java
• C

那么请使用 64 位整数类型，避免整数溢出。

例如：

• C / C++：long long
• C# / Java：long

---

样例说明

样例 1

下面展示了两个满足样例 1 测量结果的蛋糕：

• 一个体积最小；
• 一个体积最大。

---

样例输入 1

2 2
2 5
3 5

样例输出 1

11 12

---

样例输入 2

3 3
5 18 9
18 4 9

样例输出 2

41 67

测试点	层级	N	M	数据特征	标准输出	设计目的
1	弱数据	1	1	唯一高度为 1	1 1	最小规模、最小高度
2			3	单行，列最大值递增	9 9	单行退化情况
3		4	1	单列，行最大值无序	14 14	单列退化情况
4		3	4	所有最大值均为 1	12 12	基础体积，无增量
5	正常数据		2	所有最大值均为 4	15 24	大量相等值及配对扣减
6		4	5	重复值、部分值相等	50 84	检验频次配对与前缀和
7		6		无序、多组重复最大值	70 146	综合检验排序和二分查找
8	边界数据	4		含 1、999999、1000000	2500013 6500007	高度上下界及相邻值
9	较强数据	200	180	伪随机分布、重复值	201386 11419438	中等规模综合覆盖
10	极限数据	100000		所有高度均为 1000000	109999900000 10000000000000000	大规模及 long long 溢出防护