Pagini recente » Cod sursa (job #1243427) | Cod sursa (job #2472385) | Cod sursa (job #2623175) | Cod sursa (job #544004) | Cod sursa (job #2698596)
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int a[1010][1010], N, M;
int Pal[1010][2010];
void Manacher()
{
int v[2010];
for(int line = 1; line <= N; line++)
{
v[0] = -1;
for(int i = 1; i <= N; i++)
v[2 * i] = a[line][i];
v[2 * N + 2] = -2;
for(int i = 1; i <= 2 * N + 1; i += 2)
v[i] = -3;
int C = 0, R = 0;
for(int i = 1; i <= 2 * N + 1; i++)
{
int mirror = 2 * C - i;
if(i < R)
Pal[line][i] = min(Pal[line][mirror], (R - i));
while(v[i + Pal[line][i] + 1] == v[i - Pal[line][i] - 1])
Pal[line][i]++;
if(i + Pal[line][i] > R)
{
C = i;
R = i + Pal[line][i];
}
}
}
}
int main()
{
fin >> N >> M;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
fin >> a[i][j];
Manacher();
stack <int> st;
int sol = 0;
for(int j = 1; j <= 2 * M; j++)
{
for(int i = 1; i <= N; i++)
if(st.empty() || Pal[st.top()][j] <= Pal[i][j])
st.push(i);
else
{
int border;
while(!st.empty() && Pal[st.top()][j] > Pal[i][j])
{
int val = Pal[st.top()][j];
st.pop();
if(st.empty())
border = 0;
else
border = st.top();
sol = max(sol, (i - 1 - border) * val);
}
st.push(i);
}
int border;
while(!st.empty())
{
int val = Pal[st.top()][j];
st.pop();
if(st.empty())
border = 0;
else
border = st.top();
sol = max(sol, (N - border) * val);
}
}
fout << sol << '\n';
return 0;
}