#P17684. [Jboi2026]Christmas Tree
[Jboi2026]Christmas Tree
题目描述
给定一个 的整数矩阵 ,其中 表示第 行、第 列灯泡的亮度。
定义一棵高度为 ()的圣诞树。
选择格子 作为树顶的星星。圣诞树包含连续的 行:
在第 行(),圣诞树包含列
上的所有格子。
因此各层宽度依次为
整棵圣诞树必须完全位于矩阵内部。
对于 ,定义第 层的亮度集合:
$$S_d= \left\{ T[i+d][j-d], T[i+d][j-d+1], \ldots, T[i+d][j+d] \right\}.$$对于每两个相邻层,要求上层的每一个亮度都严格小于下层的每一个亮度。也就是说,对每个 :
$$\forall x\in S_d,\ \forall y\in S_{d+1},\quad x<y.$$对于每个高度
求所有恰好高度为 的合法圣诞树中,星星格子 的最大可能值。
若不存在高度为 的合法圣诞树,输出 -1。
输入格式
第一行:
N M
接下来 行,每行包含 个整数,描述矩阵 。
输出格式
输出 行。
对于 ,依次输出:
- 高度恰好为 的合法圣诞树中最大的星星亮度;
- 若不存在,输出
-1。
数据范围
子任务
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 | 3 | |
| 2 | 5 | |
| 3 | 12 | |
| 4 | 15 | |
| 5 | 19 | |
| 6 | 38 | |
| 7 | 8 | 无额外限制 |
样例
输入
4 5
5 1 4 2 7
8 9 10 11 12
18 14 20 16 17
1 1 1 1 1
输出
11
4
-1
对于高度 ,最大的星星亮度为 。它下一层的三个亮度为 ,均严格大于 。
对于高度 ,最大的合法星星亮度为 。
不存在高度 的合法圣诞树。