OpenJudge

4:子数组

总时间限制:
1000ms
内存限制:
32768kB
描述

给出一个N行N列的二维数组,元素只取0,1,2这三种值,并且每行、每列的元素值单调不下降。在此数组中,找出一个值全部等于0或者全部等于2的子二维数组,使得这个子数组的元素个数最多。子二维数组是指行数、列数不超过N的连续的一个矩形区域。

输入
第1行:1个整数N,表示二维数组的行数和列数。行的编号从1到N,列的编号从1到N。
接下来N行,每行两个整数P1和P2。P1表示在该行中第1个1所在的列编号。如果该行没有1,则P1=0. P2表示该行中第1个2所在的列编号。如果该行没有2,则P2=0
输出
第1行:1个整数,表示最大的值全部等于0或者全部等于2的子二维数组的元素个数
第2行:1个整数,表示元素个数为最大值的子数组一共有多少个
注意,如果没有满足题意的子数组,在第1行和第2行上均输出0
样例输入
8
4 0
4 8
4 8
3 7
3 6
3 5
2 3
0 2
样例输出
12
4
提示
【样例说明】
输入数据描述的二维数组是这样的:
0 0 0 1 1 1 1 1
0 0 0 1 1 1 1 2
0 0 0 1 1 1 1 2
0 0 1 1 1 1 2 2
0 0 1 1 1 2 2 2
0 0 1 1 2 2 2 2
0 1 2 2 2 2 2 2
0 2 2 2 2 2 2 2
可以看出,一共有4个值全部相同的子二维数组,分别是:(1,1)到(6,2);(5,6)到(8,8); (7,3) 到 (8,8); (6,5)到(8,8).
【数据范围】
1<=N<=5000
全局题号
16685
添加于
2018-01-27
提交次数
139
尝试人数
23
通过人数
19