小 Z 正在一张地图上选择首都的位置。地图由 N 行 M 列地块构成,第 i 行第 j 列地块的价值为 a_{i,j},地块价值可以为负数。
首都必须占据一个边长为 C 的正方形区域,即连续 C 行、连续 C 列,共 C\times C 个地块。首都的总价值等于其覆盖区域内所有地块价值之和。
请找到一个位置,使首都的总价值最大,并输出这个正方形左上角的坐标。
地图的行号和列号均从 1 开始。保证最优方案唯一。
第一行输入三个整数 N、M、C,分别表示地图的行数、列数以及首都正方形区域的边长。
接下来 N 行,每行输入 M 个整数。第 i 行第 j 列的整数 a_{i,j} 表示对应地块的价值。
数据范围:
输出两个整数 X 和 Y,用一个空格隔开,分别表示最佳正方形左上角的行号和列号。
保证最优方案唯一。
3 4 2 1 2 3 1 -1 9 0 2 2 0 1 1
1 2
3 3 2 -8 -8 -8 -8 -1 -1 -8 -1 -1
2 2
选择左上角为 (1,2)、边长为 2 的正方形,覆盖的四个地块价值为 2、3、9、0,价值和为 14。其他所有边长为 2 的正方形价值和均小于 14,因此输出 1 2。
所有地块的价值都是负数,仍需选择价值和最大的正方形。以 (2,2) 为左上角的正方形价值和为 -4,优于其他选择,因此输出 2 2。