前言

不是，题解区的题解怎么这么烂？！

解题思路

考虑用（二维）前缀和优化

下面我们讲一下什么是二维前缀和，建立在一维前缀和之上，我们要求一个矩阵内一个任意的子矩阵的数的和，我们就可以用二维前缀和，我们还是用DP来预处理，状态和一维前缀和差不多，只不过我们多加了一维。

用 $f(i,j)$ 表示 $1,1$ 这个点与 $(i,j)$ 这个点两个点分别为左上角和右下角所组成的矩阵内的数的和，则状态转移方程为：

$f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)+val_{i,j}$

其中 $val_{i,j}$ 表示 $(i,j)$ 这一格的价值。

怎么来的呢？我们画一下图就知道了。

一开始是这样的：$f(i,j)$ 为 $0$，即图中所有格子都是白色的。

回顾转移方程：$f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)+val_{i,j}$

第一个加的是 $f(i,j-1)$，所以我们将 $(1,1)$ ~ $(i,j-1)$ 染成黄色，表示加过一次。如上图所示。

此后再加上 $f(i-1,j)$，但是我们发现两次染色中有一部分是重复染色的。即：$(1,1)$~$(i-1,j-1)$，它们被染过两次色，在上图中我们将这一块区域染成棕色。

既然重复计算了，那我们就剪掉，即减去$f(i-1,j-1)$，此时 $(1,1)$~$(i-1,j-1)$ 又回归了黄色（即只染过一次色）。我们发现：只需再把 $(i,j)$ 这一格染成黄色，便大功告成了！

即加上：$val_{i,j}$，如下图：

所以我们用图解证明了转移方程 $f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)+val_{i,j}$

现在只需枚举左上角，根据边长 $c$ 算出左下角，然后用二维前缀和 $O(1)$ 更新。

附 $(x_1,y_1)$ 到 $(x_2,y_2)$ 权值和的计算方法：

$f(x_2,y_2)-f(x_2,y_1-1)-f(x_1-1,y_2)+f(x_1-1,y_1-1)$

这可以用二维前缀和的定义进行理解，或用图解也行。

完整代码不提供了，自己想吧~

请勿过度依赖题解

计算公式在这里（实在不会再查看）

// 定义常量与变量 
地块价值数组 a[10000][10000]
前缀和数组 b[10000][10000]
最大总和 maxn = -极大值
左上角行 l = 0 
左上角列 r = 0 
 
// 输入处理 
读取整数 N, M, C 
C = C - 1  // 调整边长为实际索引范围 
 
// 计算前缀和数组 
对于每一行 i 从 1 到 N:
    对于每一列 j 从 1 到 M:
        读取地块价值 a[i][j]
        //计算公式
 
// 遍历所有可能的首都位置 
对于左上角行 i 从 1 到 (N - C):
    对于左上角列 j 从 1 到 (M - C):
        计算当前区域总和：
            //计算公式
        如果 sum > maxn:
            更新最大总和 maxn = sum 
            记录坐标 l = i, r = j 
        否则如果 sum == maxn 且当前坐标更优（可选条件）:
            更新坐标 l = i, r = j 
 
// 输出结果 
输出 l 和 r