Pagini recente » Cod sursa (job #1372573) | Cod sursa (job #465910) | Cod sursa (job #2061886) | Cod sursa (job #1056394) | Cod sursa (job #2606144)
//#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dreptpal.in");
ofstream cout("dreptpal.out");
const int NMAX = 1000;
int N, M;
int a[NMAX + 2][NMAX + 2], manacher[NMAX + 2][NMAX + 2];
void Manacher(int l)
{
int drMax = 0, posDrMax = 0;
for(int i = 1; i <= M; i++)
if(i > drMax)
{
int st = i - 1, dr = i + 1;
while(st >= 1 && dr <= M && a[l][st] == a[l][dr])
st--, dr++;
st++, dr--;
manacher[l][i] = dr - i;
drMax = dr, posDrMax = i;
}
else
{
if(i + manacher[l][2 * posDrMax - i] < drMax)
manacher[l][i] = manacher[l][2 * posDrMax - i];
else
{
int st = 2 * i - drMax, dr = drMax;
while(st >= 1 && dr <= M && a[l][st] == a[l][dr])
st--, dr++;
st++, dr--;
manacher[l][i] = dr - i;
drMax = dr, posDrMax = i;
}
}
}
int ans;
vector <int> pos[NMAX + 5];
int dad[NMAX + 5], sz[NMAX + 5];
int Root(int node)
{
if(node == dad[node]) return node;
return dad[node] = Root(dad[node]);
}
void dojoin(int l, int r, int val)
{
l = Root(l);
r = Root(r);
if(l != r)
{
if(sz[l] > sz[r])
{
dad[r] = l;
sz[l] += sz[r];
ans = max(ans, sz[l] * (2 * val + 1));
}
else
{
dad[l] = r;
sz[r] += sz[l];
ans = max(ans, sz[r] * (2 * val + 1));
}
}
}
void join(int col, int line, int val)
{
if(manacher[line - 1][col] >= manacher[line][col])
dojoin(line - 1, line, val);
if(manacher[line + 1][col] >= manacher[line][col])
dojoin(line + 1, line, val);
}
int main()
{
cin >> N >> M;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
cin >> a[i][j];
for(int i = 1; i <= N; i++)
Manacher(i);
/*
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
cout << manacher[i][j] << ' ';
cout << '\n';
}
*/
for(int col = 1; col <= M; col++)
{
for(int line = 1; line <= N; line++)
{
pos[line].clear();
dad[line] = line;
sz[line] = 1;
}
for(int line = 1; line <= N; line++)
pos[manacher[line][col]].push_back(line);
for(int val = M; val >= 1; val--)
for(auto line : pos[val])
join(col, line, val);
}
cout << ans << '\n';
return 0;
}