You are given matrix a of size n × m, its elements are integers. We will assume that the rows of the matrix are numbered from top to bottom from 1 to n, the columns are numbered from left to right from 1 to m. We will denote the element on the intersecting of the i-th row and the j-th column as a ij.
We’ll call submatrix i 1, j 1, i 2, j 2 (1 ≤ i 1 ≤ i 2 ≤ n; 1 ≤ j 1 ≤ j 2 ≤ m) such elements a ij of the given matrix that i 1 ≤ i ≤ i 2 AND j 1 ≤ j ≤ j 2. We’ll call the area of the submatrix number (i 2 - i 1 + 1)·(j 2 - j 1 + 1). We’ll call a submatrix inhomogeneous, if all its elements are distinct.
Find the largest (in area) inhomogenous submatrix of the given matrix.
Input
The first line contains two integers n, m (1 ≤ n, m ≤ 400) — the number of rows and columns of the matrix, correspondingly.
Each of the next n lines contains m integers a ij (1 ≤ a ij ≤ 160000) — the elements of the matrix.
Output
Print a single integer — the area of the optimal inhomogenous submatrix.
Examples
input
3 3
1 3 1
4 5 6
2 6 1
output
6
input
3 4
5 2 3 1
3 3 5 3
4 4 4 5
output
4
input
2 6
1 2 3 4 5 6
8 6 7 8 9 1
output
8
Solution:
#include <iostream> #include <iomanip> #include <cstdio> #include <set> #include <vector> #include <map> #include <cmath> #include <algorithm> #include <memory.h> #include <string> #include <cstring> #include <sstream> #include <cstdlib> #include <ctime> #include <cassert> using namespace std; const int N = 444; const int M = N * N; short f[N][N][N]; inline void add(int xa, int ya, int xb, int yb) { yb--; if (yb < f[xa][xb][ya]) { f[xa][xb][ya] = yb; } } int last[M], was[M]; int a[N][N]; int main() { int r, c; scanf("%d %d", &r, &c); for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) scanf("%d", a[i] + j); for (int i1 = 1; i1 <= r; i1++) for (int i2 = i1; i2 <= r; i2++) for (int j = 1; j <= c; j++) f[i1][i2][j] = c; for (int i = 0; i < M; i++) { last[i] = 0; was[i] = 0; } int it = 0; for (int i = 1; i <= r; i++) { it++; for (int j = c; j >= 1; j--) { if (was[a[i][j]] == it) { add(i, j, i, last[a[i][j]]); } last[a[i][j]] = j; was[a[i][j]] = it; } } for (int i1 = 1; i1 <= r; i1++) { for (int i2 = i1 + 1; i2 <= r; i2++) { it++; for (int j = c; j >= 1; j--) { if (was[a[i1][j]] == it) { add(i1, j, i2, last[a[i1][j]]); } last[a[i1][j]] = j; was[a[i1][j]] = it; if (was[a[i2][j]] == it) { add(i1, j, i2, last[a[i2][j]]); } last[a[i2][j]] = j; was[a[i2][j]] = it; } } } int ans = 0; for (int i1 = r; i1 >= 1; i1--) for (int i2 = i1; i2 <= r; i2++) for (int j = c; j >= 1; j--) { int ft = f[i1][i2][j]; int area = (i2 - i1 + 1) * (ft - j + 1); if (area > ans) { ans = area; } if (i1 > 1 && ft < f[i1 - 1][i2][j]) { f[i1 - 1][i2][j] = ft; } if (i2 < r && ft < f[i1][i2 + 1][j]) { f[i1][i2 + 1][j] = ft; } if (j > 1 && ft < f[i1][i2][j - 1]) { f[i1][i2][j - 1] = ft; } } printf("%d\n", ans); return 0; }