063 - Monochromatic Subgrid（★4）
Editorial
/ 
/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点: 4 点
問題文
縦 H 行、横 W 列のグリッドがあり、上から i 行目、左から j 列目のマスを (i, j) で表します。マス (i, j) には整数 P_{i, j} が書かれています。
さて、このグリッドから（連続するとは限らない）1 つ以上の行と 1 つ以上の列を選ぶことでできる「部分グリッド」であって、次の条件を満たすものを良い部分グリッドと呼びます。
条件 選んだ行を i_1, i_2, \dots, i_A \ (1 \leq i_1 < i_2 < \dots < i_A \leq H) とし、選んだ列を j_1, j_2, \dots, j_B \ (1 \leq j_1 < j_2 < \dots < j_B \leq W) とすると、マス (i_a, j_b) \ (1 \leq a \leq A, 1 \leq b \leq B) に書かれている整数はすべて同じである。
良い部分グリッドの大きさとしてあり得る最大値を求めてください。
ただし A 個の行・B 個の列からなる部分グリッドの大きさは A \times B であるとします。
制約
- 1 \leq H \leq 8
- 1 \leq W \leq 10000
- 1 \leq P_{i, j} \leq HW
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
H W
P_{1, 1} P_{1, 2} \cdots P_{1, W}
P_{2, 1} P_{2, 2} \cdots P_{2, W}
\vdots
P_{H, 1} P_{H, 2} \cdots P_{H, W}
出力
良い部分グリッドの大きさとしてあり得る最大値を出力してください。
入力例 1
4 6 1 1 1 1 1 2 1 2 2 2 2 2 1 2 2 3 2 3 1 2 3 2 2 3
出力例 1
6
\{2, 3\} 行目と \{2, 3, 5\} 列目を選ぶことでできる大きさ 6 の部分グリッドは、次のように全てのマスに 2 が書かれています。
. . . . . . . 2 2 . 2 . . 2 2 . 2 . . . . . . .
したがって、この部分グリッドは良い部分グリッドであり、これより大きな良い部分グリッドは存在しないため 6 を出力します。
入力例 2
3 3 1 2 3 4 5 6 7 8 9
出力例 2
1
入力例 3
5 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
出力例 3
15