题解

思路

分别处理四个射击方向；对于一个固定方向，核心是快速统计所有起点对应的曼哈顿三角形。

做法

暴力与部分分

枚举起点、方向和所有目标即可完成 $n m\le100$。若 $k\le20$，固定右下方向和起点后，枚举向下走的行数，并用行前缀和统计该行可覆盖的连续区间；四次翻转方格即可覆盖四个方向，复杂度为 $O(nmk)$。

满分算法

仍只考虑右下方向。令 $f_{i,j}$ 表示以 $(i,j)$ 为起点的右下三角形中的目标数。$f_{i+1,j}$ 比所需区域多出斜边 $x+y=i+j+k+1$，而缺少第 $i$ 行从 $j$ 开始、长度至多 $k+1$ 的一段，因此

$$f_{i,j}=f_{i+1,j}+\operatorname{row}(i,j,j+k)-\operatorname{diag}(i+j+k+1).$$

预处理每行前缀和与右上到左下斜线前缀和，就能在 $O(1)$ 时间得到两个区间和。把方格分别上下翻转、左右翻转以及同时翻转，四次计算右下方向的最大值，即得到四个方向的答案。

正确性说明

递推中的两个三角形内部完全重合；唯一新增的是当前行的合法横段，唯一多算的是距离恰为 $k+1$ 的斜边，故递推精确计算右下射击区域。翻转是格子间的双射，并保持曼哈顿距离，所以四种翻转后的右下区域恰好对应原图四个方向。枚举所有起点取最大值即为最优答案。

复杂度

四次扫描均为 $O(nm)$，总时间复杂度 $O(nm)$，空间复杂度 $O(nm)$。