A83457.方形小区

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小镇准备划分新的居住区。镇长拿到了一张 n×nn\times n 的人口热力图,第 ii 行第 jj 列的整数表示该格子的“人口活跃度”。
现在需要在图上选择一个 边长为 mm 的正方形区域 作为新居住区,使得该区域内所有格子的活跃度总和尽可能大。请你输出这个最大总和。

输入格式

第一行:两个整数 n,mn, m(表示地图大小与选择的正方形边长)。

接下来 nn 行:每行 nn 个整数,表示热力图的活跃度。

输出格式

输出一个整数,表示所有边长为 mm 的正方形子矩形中,元素和的最大值。

输入输出样例

  • 输入#1

    4 2
    1 2 3 4
    5 6 7 8
    0 1 0 1
    9 9 9 9
    

    输出#1

    22

说明/提示

  • 1n10001 \le n \le 1000

  • 1mn1 \le m \le n

  • 每个格子的值为 0ai,j1040 \le a_{i,j} \le 10^4

对于样例:
所有 2×22\times 2 的方形区域中,最大的是右上角这个子矩形:

3 47 83 \ 4 \\ 7 \ 8

和为 3+4+7+8=223 + 4 + 7 + 8 = 22

首页