Pagini recente » Cod sursa (job #1463836) | Cod sursa (job #2154668) | Cod sursa (job #70043) | Cod sursa (job #410917) | Cod sursa (job #1661454)
#include<fstream>
using namespace std;
const int N = 1010;
int A[N][N];
int P[N][N];
int jump[N];
int latura[N];
void Manacher(int n, int m) {
int i, j, l, r;
for(i = 1; i <= n; ++ i) {
l = 0;
r = 0;
for(j = 1; j <= m; ++ j) {
if(j <= r)
P[i][j] = min(P[i][2 * l - j], r - j);
while(j - P[i][j] > 1 && j + P[i][j] < m && A[i][j - P[i][j] - 1] == A[i][j + P[i][j] + 1])
++ P[i][j];
if(j + P[i][j] > r) {
r = j + P[i][j];
l = j;
}
}
}
}
int main() {
ifstream cin("dreptpal.in");
ofstream cout("dreptpal.out");
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, m;
int i, j;
int k, ret;
cin >> n >> m;
for(i = 1; i <= n; ++ i)
for(j = 1; j <= m; ++ j)
cin >> A[i][j];
Manacher(n, m);
ret = 0;
for(j = 1; j <= m; ++ j) {
for(i = 1; i <= n; ++ i) {
k = i - 1;
while(k >= 1 && P[k][j] >= P[i][j])
k = jump[k];
jump[i] = k;
latura[i] = i - k;
}
for(i = n; i >= 1; -- i) {
k = i + 1;
while(k <= n && P[k][j] >= P[i][j])
k = jump[k];
jump[i] = k;
latura[i] += k - i;
}
for(i = 1; i <= n; ++ i)
ret = max((latura[i] - 1) * (2 * P[i][j] + 1), ret);
}
cout << ret << '\n';
return 0;
}