Pagini recente » Cod sursa (job #167151) | Cod sursa (job #2358555) | Cod sursa (job #146778) | Cod sursa (job #1876237) | Cod sursa (job #2698581)
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int a[1005][1005];
short int Pal[2005][2005], N, M;
void Manacher()
{
int v[2005];
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], (short int)(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
{
sol = max(sol, (int)Pal[st.top()][j]);
st.pop();
int border;
while(!st.empty() && Pal[st.top()][j] > Pal[i][j])
{
if(st.empty())
border = 0;
else
border = st.top();
sol = max(sol, (int)Pal[st.top()][j] * (i - border)); /// poz4; poz5; poz6
st.pop();
}
st.push(i);
}
sol = max(sol, (int)Pal[st.top()][j]);
st.pop();
int border;
while(!st.empty())
{
if(st.empty())
border = 0;
else
border = st.top();
sol = max(sol, (int)Pal[st.top()][j] * (N - border));
st.pop();
}
}
fout << sol << '\n';
return 0;
}