P14040 [PAIO 2025] Exhibition

你是一场著名艺术展览的策展人。你有 $N$ 幅画作，每幅画有两个属性：画作尺寸 $A_i$ 和艺术价值 $B_i$。你还有 $M$ 个可用的画框，每个画框有尺寸 $S_j$。 你希望选择并安排 $k$ 幅画作 $i_1, i_2, \dots, i_k$ 以及画框 $j_1, j_2, \dots, j_k$ 进行展示，要求满足： - 每一幅选中的画作 $i_t$ 放在画框 $j_t$ 中，且画作尺寸不能大于画框尺寸：$A_{i_t} \le S_{j_t}$。 - 选中的画作尺寸按照展示顺序非递减排列：$A_{i_1} \le A_{i_2} \le \dots \le A_{i_k}$。 - 选中的画作艺术价值按照展示顺序非递减排列：$B_{i_1} \le B_{i_2} \le \dots \le B_{i_k}$。 请你求出能够满足上述条件的最大 $k$ 值。 ### 实现细节 你需要实现如下函数： ```c int32 max_paintings(int32 N, int32 M, int32[] A, int32[] B, int32[] S) ``` - $N$：画作数量 - $M$：画框数量 - $A$：长度为 $N$ 的数组，第 $i$ 个元素为第 $i$ 幅画作的尺寸 - $B$：长度为 $N$ 的数组，第 $i$ 个元素为第 $i$ 幅画作的艺术价值 - $S$：长度为 $M$ 的数组，第 $j$ 个元素为第 $j$ 个画框的尺寸 - 函数返回能够展示的最大的画作数量

第一行：两个整数 $N$ 和 $M$ 第二行：$N$ 个整数 $A_1, A_2, \dots, A_N$（画作尺寸） 第三行：$N$ 个整数 $B_1, B_2, \dots, B_N$（艺术价值） 第四行：$M$ 个整数 $S_1, S_2, \dots, S_M$（画框尺寸）

输出一个整数，表示能够展示的最大画作数量。

### 样例 调用 `max_paintings(3, 3, [1, 2, 3], [1, 2, 4], [2, 3, 5])` 应返回 `3`。 - 有三幅画，尺寸为 $[1, 2, 3]$，艺术价值为 $[1, 2, 4]$。 - 有三个画框，尺寸为 $[2, 3, 5]$。 - 可以选全部三幅画：画作1（尺寸1，价值1）放在画框1（尺寸2），画作2（尺寸2，价值2）放在画框2（尺寸3），画作3（尺寸3，价值4）放在画框3（尺寸5）。 - 尺寸递增：$1 \le 2 \le 3$，艺术价值递增：$1 \le 2 \le 4$。 调用 `max_paintings(4, 3, [1, 3, 2, 4], [3, 2, 3, 5], [3, 6, 4])` 应返回 `3`。 - 有四幅画，尺寸为 $[1, 3, 2, 4]$，艺术价值为 $[3, 2, 3, 5]$。 - 有三个画框，尺寸为 $[3, 6, 4]$。 - 可以选择第1、3、4幅画：画作1（尺寸1，价值3）放在画框1（尺寸3），画作3（尺寸2，价值3）放在画框3（尺寸4），画作4（尺寸4，价值5）放在画框2（尺寸6）。 - 尺寸递增：$1 \le 2 \le 4$，艺术价值递增：$3 \le 3 \le 5$。 调用 `max_paintings(4, 3, [1, 3, 2, 4], [3, 2, 3, 5], [1, 1, 4])` 应返回 `2`。 - 有四幅画，尺寸为 $[1, 3, 2, 4]$，艺术价值为 $[3, 2, 3, 5]$。 - 有三个画框，尺寸为 $[1, 1, 4]$。 - 可以选择画作1（尺寸1，价值3）放在画框1或2（尺寸1），再选择画作4（尺寸4，价值5）放在画框3（尺寸4）。 - 尺寸递增：$1 \le 4$，艺术价值递增：$3 \le 5$。 ### 测试器说明 样例测试器按照如下格式读取输入： - 第1行：两个整数 $N$ 和 $M$ - 第2行：$N$ 个整数 $A_1, A_2, \dots, A_N$（画作尺寸） - 第3行：$N$ 个整数 $B_1, B_2, \dots, B_N$（艺术价值） - 第4行：$M$ 个整数 $S_1, S_2, \dots, S_M$（画框尺寸） 测试器会调用 `max_paintings(N, M, A, B, S)` 并输出返回值。 注意：本问题所附的样例测试器仅用于本地测试，正式测评环境可能与之不同。 ### 数据范围 - $1 \le N, M \le 10^5$ - $1 \le A_i, B_i, S_j \le 10^9$ ### 评分 - 子任务 1（10 分）：$N, M \le 10$ - 子任务 2（20 分）：所有画框尺寸都大于所有画作尺寸（对任意 $i,j$，有 $S_j > A_i$） - 子任务 3（20 分）：所有艺术价值相等（任意 $i,j$ 有 $B_i = B_j$） - 子任务 4（20 分）：$N, M < 2000$ - 子任务 5（30 分）：无额外限制 由 ChatGPT 5 翻译