AT_gw2015_i.ピラミッド - 立方体編

伊织酱最近迷上了建造金字塔。

由于已经对用球形石头建造金字塔感到厌烦，她这次选择使用边长为 $1$ 的立方体石头。建造的步骤如下：

• 在纸上绘制一个 $N \times N$ 的网格。每个格子的边长都是 $1$。第 $i$ 行第 $j$ 列的格子记为 $(i, j)$。
• 在每个格子上竖直堆叠至少一个石头。格子 $(i, j)$ 上堆叠的石头数量为 $H_{i,j}$。
• 选择一个格子作为中心，记为格子 $P$。
• 移除一些石头（可以不移除），使得剩下的石头能形成以格子 $P$ 为中心的金字塔。

定义：石头以格子 $P$ 为中心形成金字塔时，需满足以下条件：

• 将格子 $P$ 记作 $(Pi, Pj)$，格子 $(i, j)$ 上的石头数记为 $S_{i,j}$，$S_{Pi, Pj}$ 记为 $T$。对于所有的 $i$ 和 $j$，以下条件需要成立：
  • $S_{i,j} = \max(0, T - \max(|Pi - i|, |Pj - j|))$
  • $S_{i,j} \le \min(Pi, Pj, N - Pi + 1, N - Pj + 1)$

在这种情况下，称格子 $P$ 上的石头数为金字塔的高度。

你的任务是，对于每个格子 $(i, j)$，找出以它为中心所能形成的最大金字塔高度，并计算这些最大高度的总和。

输入包含多个测试用例：

• 第一行为两个整数 $N$ 和 $Q$，分别表示网格的边长和测试用例的数量。$(1 \le N \le 500, \ 1 \le Q \le 10)$
• 第二行为四个整数 $X, A, B, C$，用于生成测试用例的随机数。（$0 \le X < 2^{31}$）
• 接下来的 $N$ 行，每行包含 $N$ 个整数，表示每个格子初始堆叠的石头数。其中，第 $i$ 行的第 $j$ 个数为 $H_{i,j}$，表示格子 $(i, j)$ 上堆叠的石头数。$(1 \le H_{i,j} \le N)$

输出包含 $Q$ 行，每行对应一个测试用例的答案，即该测试用例所有格子的最大金字塔高度之和。每行末尾应有换行符。

样例解释

对于给定的测试用例，计算每个格子的最大金字塔高度，并将这些最大高度的和输出为该测试用例的结果。例如，第一个测试用例的结果是 $35$，第二个是 $27$，第三个是 $30$。

本翻译由 AI 自动生成