A83457.方形小区
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小镇准备划分新的居住区。镇长拿到了一张 n×n 的人口热力图,第 i 行第 j 列的整数表示该格子的“人口活跃度”。
现在需要在图上选择一个 边长为 m 的正方形区域 作为新居住区,使得该区域内所有格子的活跃度总和尽可能大。请你输出这个最大总和。
输入格式
第一行:两个整数 n,m(表示地图大小与选择的正方形边长)。
接下来 n 行:每行 n 个整数,表示热力图的活跃度。
输出格式
输出一个整数,表示所有边长为 m 的正方形子矩形中,元素和的最大值。
输入输出样例
输入#1
4 2 1 2 3 4 5 6 7 8 0 1 0 1 9 9 9 9
输出#1
22
说明/提示
-
1≤n≤1000
-
1≤m≤n
-
每个格子的值为 0≤ai,j≤104
对于样例:
所有 2×2 的方形区域中,最大的是右上角这个子矩形:
3 47 8
和为 3+4+7+8=22。