Pagini recente » Cod sursa (job #2135573) | Cod sursa (job #1370121) | Cod sursa (job #1929173) | Cod sursa (job #2943116) | Cod sursa (job #2555420)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1005;
int N, M;
int a[NMAX][NMAX], palin[NMAX][NMAX];
void Manacher(int line)
{
int left, right, k;
left = 0, right = 0;
for (int i = 1;i <= M;++i)
{
if (i > right)
{
k = 1;
while (i - k >= 1 && i + k <= M && a[line][i - k] == a[line][i + k])
++k;
palin[line][i] = k;
}
else
{
k = palin[line][left + right - i];
if (i + k - 1 < right)
palin[line][i] = k;
else
{
k = right - i;
while (i - k >= 1 && i + k <= M && a[line][i - k] == a[line][i + k])
++k;
palin[line][i] = k;
}
}
}
}
int st[NMAX], top, stg[NMAX], drp[NMAX], v[NMAX], answer;
void Solve(int col)
{
for (int i = 1;i <= N;++i)
v[i] = palin[i][col];
top = 0;
v[0] = -1;
st[top] = 0;
for (int i = 1;i <= N;++i)
{
while (top > 0 && v[i] <= v[st[top]])
--top;
stg[i] = i - st[top];
st[++top] = i;
}
top = 0;
v[N + 1] = -1;
st[top] = N + 1;
for (int i = N;i >= 1;--i)
{
while (top > 0 && v[i] <= v[st[top]])
--top;
drp[i] = st[top] - i;
st[++top] = i;
}
for (int i = 1;i <= N;++i)
answer = max(answer, (2 * v[i] - 1) * (stg[i] + drp[i] - 1));
}
int main()
{
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
fin >> N >> M;
for (int i = 1;i <= N;++i)
for (int j = 1;j <= M;++j)
fin >> a[i][j];
for (int i = 1;i <= N;++i)
Manacher(i);
for (int j = 1;j <= M;++j)
Solve(j);
fout << answer << "\n";
fin.close();
fout.close();
return 0;
}