#T273. 最大值的位置

最大值的位置

给定一个 nn 行 mm 列的整数矩阵,请找出矩阵中的最大值,并输出这个值以及它第一次出现的位置。

矩阵的行从上到下依次编号为 1,2,…,n1,2,\dots,n,列从左到右依次编号为 1,2,…,m1,2,\dots,m。本题所说的位置一律用行号和列号描述,且两者都从 11 开始。

最大值可能在矩阵中出现多次。此时规定:位置按行优先顺序比较,先比行号,行号小的更靠前;行号相同时再比列号,列号小的更靠前。也就是说,从第 11 行开始逐行向下扫描,每行内从左到右扫描,第一次遇到最大值的位置就是答案位置。等价地说,所有达到最大值的格子中,取行号最小的;若有多个格子的行号都最小,再取其中列号最小的。

输入格式

第一行两个整数 nn(1≤n≤2001\le n\le 200)和 mm(1≤m≤2001\le m\le 200),分别表示矩阵的行数与列数,两个整数之间用一个空格分隔。

接下来 nn 行,每行 mm 个整数,同一行内相邻整数之间用一个空格分隔,行末没有多余空格。第 ii 行第 jj 个整数为 ai,ja_{i,j}(−109≤ai,j≤109-10^9\le a_{i,j}\le 10^9),表示矩阵第 ii 行第 jj 列的元素。

输出格式

输出一行三个整数,相邻两个整数之间用一个空格分隔,行末输出换行符。三个整数依次是:

  1. 矩阵所有元素中的最大值;
  2. 该最大值第一次出现时所在的行号;
  3. 该最大值第一次出现时所在的列号。

因为行优先规则唯一确定了位置,本题的正确答案完全唯一。不要输出其他内容。

数据范围

  • 1≤n≤2001\le n\le 200,1≤m≤2001\le m\le 200,矩阵最多有 200×200=40000200\times 200=40000 个元素。
  • 对每个 1≤i≤n1\le i\le n 与 1≤j≤m1\le j\le m,都有 −109≤ai,j≤109-10^9\le a_{i,j}\le 10^9。
  • 元素可以是负数、零,也可以重复出现;同一个值可能出现多次。

样例

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

最大值为 77,它在矩阵中出现了 44 次,位置分别是第 11 行第 22 列、第 11 行第 44 列、第 22 行第 33 列、第 33 行第 33 列。其中行号最小的是第 11 行,第 11 行里列号最小的是第 22 列,所以第一次出现的位置是第 11 行第 22 列。

2 3
-5 -1 -9
-1 -7 -3
-1 1 2

所有元素都是负数,最大值为 −1-1。它出现在第 11 行第 22 列和第 22 行第 11 列,两处行号不同,行号小的更靠前,因此输出第 11 行第 22 列。注意这里不能按列号优先比较:第 22 行第 11 列的列号更小,但它不是行优先顺序下的第一次出现。

1 1
-1000000000
-1000000000 1 1

矩阵只有一个元素,此时它既是最大值,也是唯一的出现位置,行号和列号都是 11。

说明

  • 输出中的行号、列号都是题目中的 11 起始编号。若在 C++ 里用从 00 开始的下标记录位置,输出前需要各自加 11。
  • 最大值本身可能是负数,所以不能用「初始最大值取 00」的写法。
  • 本题时限 1000 ms,内存 256 MiB。