P15892 [COCI 2025/2026 #6] 教室 / Učionica

$k$ 个朋友进入一间教室。已知每个朋友的身高 $h_i$，也已知教室内其他所有学生的身高。 教室可以表示为一个 $n \times m$ 的网格 $a$，每个单元格对应一个座位。第 $i$ 行第 $j$ 列的座位记作 $a_{i,j}$。对于每个座位，我们知道它是否已被学生占据（以及占据者的身高），或者为空座。 这 $k$ 个朋友想要在教室内就坐。每个朋友占据恰好一个空座，且不能有两个朋友坐在同一个座位上。此外，他们希望坐在同一行的连续座位上。更精确地说，他们选择一个行号 $i$（$1 \le i \le n$）和一个列号 $j$（$1 \le j \le m - k + 1$），然后坐在座位 $a_{i,j}, a_{i,j+1}, \dots, a_{i,j+k-1}$ 上。朋友们可以以任意顺序就坐；他们不必按照给定的身高顺序就坐。 一个朋友认为某个座位合适，仅当所有坐在他们前面（即同一列中行号较小的座位）的学生都比他们矮，确保他们有清晰的视线。一组朋友认为某个包含 $k$ 个连续座位的集合合适，当且仅当这组朋友可以安排自己，使得每个人都能获得清晰的视线。 综合考虑这些条件，教室内有多少组适合这群朋友的连续座位集合？

第一行包含三个自然数 $n$、$m$ 和 $k$（$1 \le n, m \le 2000, 1 \le k \le m$），分别表示教室的行数、列数以及朋友的数量。 第二行包含 $k$ 个自然数 $h_1, h_2, \dots, h_k$，表示朋友的身高。 接下来的 $n$ 行，每行包含 $m$ 个自然数：如果 $a_{i,j} = 0$，则该座位为空；如果 $a_{i,j} \ge 1$，则该座位已被一个身高为 $a_{i,j}$ 的学生占据（$1 \le a_{i,j} \le 10^9$）。

输出一行一个整数，表示在同一行中连续的 $k$ 个座位的集合数量，使得这些朋友可以安排就坐后每个人都能获得清晰的视线。

**第一个样例的解释**： 两位朋友可以坐在第一行的第一和第二个座位、第二行的第二和第三个座位，或者第二行的第三和第四个座位。因此，他们可以坐在总共 $3$ 组不同的座位集合中。 **第二个样例的解释**： 四位朋友可以坐在仅有的四个空位上，只要他们按身高从矮到高排列。 **第三个样例的解释**： 由于教室内没有其他学生，三位朋友可以坐在同一行的任意三个连续座位上，因此共有 $15$ 种合适的座位安排。 **计分方式** | 子任务 | 分值 | 约束条件 | |:-------:|:------:|---------------------------| | 1 | 11 | $k \le 2$ | | 2 | 13 | $n, m \le 200$ | | 3 | 29 | $n, m \le 500$ | | 4 | 57 | 无额外限制。 | 翻译由 DeepSeek V3.2 完成