AT_abc005_4 [ABC005D] おいしいたこ焼きの焼き方

高桥君的章鱼烧店里使用的章鱼烧烤盘有一个很大的特点：不同位置烤出来的章鱼烧美味程度不同。 另外，根据店员的能力，每次能烤的章鱼烧数量也不同。 高桥君希望让每位店员都能尽可能烤出最美味的章鱼烧。 章鱼烧烤盘是一个 $N \times N$ 的正方形。 每个位置都有一个对应的章鱼烧美味度 $D_{ij}$。 每位店员每次最多能烤 $P_k$ 个章鱼烧。 每次烤的章鱼烧必须是烤盘上的一个矩形区域，并且该区域内的所有位置都要用上。 请你对于每位店员，求出他一次能烤出的章鱼烧美味度总和的最大值。 注意，每位店员开始烤的时候，烤盘是完全空的，可以选择任意位置。 输入格式如下所示。 > $N$ > $D_{11}$ $D_{12}$ ... $D_{1N}$ > $D_{21}$ $D_{22}$ ... $D_{2N}$ > ... > $D_{N1}$ $D_{N2}$ ... $D_{NN}$ > $Q$ > $P_1$ > $P_2$ > ... > $P_Q$ - 第 1 行输入一个整数 $N$，表示章鱼烧烤盘的边长，$1 \leq N \leq 50$。 - 接下来的 $N$ 行，每行输入 $N$ 个整数 $D_{ij}$，表示每个位置的章鱼烧美味度，$1 \leq D_{ij} \leq 100$。 - 接下来一行输入一个整数 $Q$，表示店员人数，$1 \leq Q \leq N^2$。 - 接下来的 $Q$ 行，每行输入一个整数 $P_k$，表示第 $k$ 位店员一次最多能烤的章鱼烧数量，$1 \leq P_k \leq N^2$。 对于每位店员，输出他一次能烤出的章鱼烧美味度总和的最大值。 每个答案输出后请换行。 如果你能正确解决所有 $1 \leq N \leq 5$ 的测试点，可以获得满分 $100$ 分中的 $50$ 分。 示例： ``` 3 3 2 1 2 2 1 1 1 1 3 1 4 9 ``` ``` 3 9 14 ``` - 第 1 位店员在左上角烤章鱼烧时美味度总和为 $3$。 - 第 2 位店员在左上角 $2 \times 2$ 的区域烤章鱼烧时美味度总和为 $9$。 - 第 3 位店员可以用整个烤盘，最大美味度总和为 $14$。 这属于部分分的输入。 ``` 3 1 1 1 1 1 1 9 9 9 1 4 ``` ``` 27 ``` - 在最下方一行 $1 \times 3$ 的区域烤章鱼烧时美味度总和为 $27$。 - 这位店员最多能烤 $4$ 个章鱼烧，但只烤 $3$ 个反而美味度更高。 这属于部分分的输入。

第 1 行：一个整数 $N$，表示烤盘的边长。 接下来 $N$ 行：每行 $N$ 个整数 $D_{ij}$，表示每个位置的美味度。 接下来一行：一个整数 $Q$，表示店员人数。 接下来 $Q$ 行：每行一个整数 $P_k$，表示每位店员一次最多能烤的章鱼烧数量。

对于每位店员，输出他一次能烤出的章鱼烧美味度总和的最大值，每个答案一行。

- 对于 $1 \leq N \leq 5$ 的所有测试点，答对即可获得 $50$ 分。 - 你可以选择比 $P_k$ 更小的矩形区域，只要美味度总和更高即可。 - 每次烤的章鱼烧必须是烤盘上的一个矩形区域，且区域内所有位置都要用上。 - 每位店员开始烤的时候，烤盘是完全空的，可以选择任意位置。 由 ChatGPT 4.1 翻译