Pagini recente » Cod sursa (job #3244101) | Cod sursa (job #2121127) | Cod sursa (job #2888810) | Cod sursa (job #504120) | Cod sursa (job #3209703)
#include <iostream>
#include <fstream>
#include <stack>
#define N 1005
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int a[N][N], lps[N][N], l[N], r[N], v[N], n, m, mx;
void Manacher(int a[], int lps[])
{
int i, st, dr;
st = dr = 1;
a[0] = -2e9; a[m + 1] = 2e9;
for (i = 1; i <= m; i++)
{
lps[i] = max(0, min(dr - i, lps[st + (dr - i)]));
while (a[i - lps[i]] == a[i + lps[i]])
lps[i]++;
if (i + lps[i] > dr)
{
st = i - lps[i];
dr = i + lps[i];
}
}
}
void SmecherieCuStDr()
{
stack <int> st;
int i;
v[0] = v[n + 1] = -1;
for (i = 1; i <= n; i++)
v[i] = 2 * v[i] - 1;
st.push(0);
for (i = 1; i <= n; i++)
{
while (v[i] <= v[st.top()])
st.pop();
l[i] = st.top();
st.push(i);
}
while (!st.empty())
st.pop();
st.push(n + 1);
for (i = n; i >= 1; i--)
{
while (v[i] <= v[st.top()])
st.pop();
r[i] = st.top();
st.push(i);
}
for (i = 1; i <= n; i++)
mx = max(mx, v[i] * (r[i] - l[i] - 1));
}
int main()
{
int i, j;
fin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
fin >> a[i][j];
for (i = 1; i <= n; i++)
Manacher(a[i], lps[i]);
for (j = 1; j <= m; j++)
{
for (i = 1; i <= n; i++)
v[i] = lps[i][j];
SmecherieCuStDr();
}
fout << mx << "\n";
fout.close();
return 0;
}