问题 5518 --机器人走方格(数不清第几版了)

5518: 机器人走方格(数不清第几版了)

时间限制: 5 Sec  内存限制: 512 MB
提交: 9  解决: 5
[提交][状态][命题人:]

题目描述

机器人走方格是经典的算法竞赛题目,和01背包问题类似,其有许多版本的变种。
现在,你需要解决以一个数不清是第几版的问题。

有一个 n 行 m 列的方格图,每个格子上有一个数字,表述该格子的权值。现在有 2 个机器人各选择一行(可以是相同的一行),同时同速度从各自选择的一行的最左边格子走向最右边的格子。每当2 个机器人各到达一个新格子后,你选择其中一个机器人,令其记录下所在格子的权值,另一个未被选择的机器人不记录。

当 2 个机器人都走到最右边的格子时,他们记录的所有权值的最小值即是他们的成绩。求在成绩最大时,两个机器人选择了哪两行。

输入

第一行包含两个正整数 n,m (1≤n≤3⋅10^5, 1≤m≤8) ,表示方格图的行列数。
接下来 n 行,每行包含 m 个整数。第 i 行的第 j 个整数为 a[i][j] (0≤a[i][j]≤10^9) 。

输出

输出两个整数 i,j (1≤i≤j≤n) 表示成绩最大的情况下,两个机器人选择的行编号。如果有多组解,输出任意一组即可。
样例输入
Copy
6 5
5 0 3 1 2
1 8 9 1 3
1 2 3 4 5
9 1 0 3 7
2 3 0 6 3
6 4 1 7 0
样例输出
Copy
1 5

提示

来源

[提交][状态]