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

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

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

题目描述**:

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

输入格式**:

第一行包含三个整数 NNMMkk2N,M10002 \leq N, M \leq 10001kmin(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% 的数据,1N,M101 \leq N, M \leq 101kmin(N,M)1 \leq k \leq \min(N, M)
  • 60% 的数据,1N,M5001 \leq N, M \leq 5001kmin(N,M)1 \leq k \leq \min(N, M)
  • 100% 的数据,1N,M10001 \leq N, M \leq 10001kmin(N,M)1 \leq k \leq \min(N, M)