241973 - 领地选择

题目描述

小 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} 表示对应地块的价值。

数据范围:

  • 1\le N,M\le 1000;
  • 1\le C\le \min(N,M);
  • -32767\le a_{i,j}\le 32767。
输出

输出两个整数 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

选择左上角为 (1,2)、边长为 2 的正方形,覆盖的四个地块价值为 2、3、9、0,价值和为 14。其他所有边长为 2 的正方形价值和均小于 14,因此输出 1 2。

样例解释 2

所有地块的价值都是负数,仍需选择价值和最大的正方形。以 (2,2) 为左上角的正方形价值和为 -4,优于其他选择,因此输出 2 2。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 3
通过人数 3
金币数量 3 枚
难度 入门


上一题 下一题