#1157. [育华]校园最大价值正方形

[育华]校园最大价值正方形

题目名称**:校园最大价值正方形

题目描述**:

育华学校正在对校园内的一块矩形场地进行价值评估与规划,这块场地呈现为 N×MN \times M 的矩形形状,场地中的每一块小区域(可看作是一个单位方格)都被赋予了一定的价值,价值范围在 −109-10^9 到 10910^9 之间。现在学校希望从这块场地中找出一个边长为 kk 的正方形区域,使得该正方形区域内所有小方格价值总和最大,以此来确定最具价值的这部分场地,为后续校园建设等相关事宜提供参考。

输入格式**:

第一行包含三个整数 NN、MM 和 kk(2≤N,M≤10002 \leq N, M \leq 1000,1≤k≤min⁡(N,M)1 \leq k \leq \min(N, M)),分别表示矩形场地的行数、列数以及要寻找的正方形区域的边长。 接下来的 NN 行,每行包含 MM 个整数,代表对应位置小区域的价值。

输出格式**:

输出一个整数,表示所找到的边长为 kk 的正方形区域的最大价值总和。

样例输入**:

4 5 2
1 -2 3 -1 4
-2 4 -1 2 -3
3 -3 2 1 -2
5 -1 -2 3 1

样例输出**:

4

数据范围**:

  • 30% 的数据,1≤N,M≤101 \leq N, M \leq 10,1≤k≤min⁡(N,M)1 \leq k \leq \min(N, M)
  • 60% 的数据,1≤N,M≤5001 \leq N, M \leq 500,1≤k≤min⁡(N,M)1 \leq k \leq \min(N, M)
  • 100% 的数据,1≤N,M≤10001 \leq N, M \leq 1000,1≤k≤min⁡(N,M)1 \leq k \leq \min(N, M),