Pagini recente » Cod sursa (job #161433) | Cod sursa (job #1870007) | Cod sursa (job #147849) | Formatare Textile | Cod sursa (job #1818398)
#include <cstdio>
#define MAXN 1000
int n, m, man[MAXN+1][MAXN+1], v[MAXN+1][MAXN+1], left[MAXN+1][MAXN+1], right[MAXN+1][MAXN+1], st[MAXN+1];
inline int minim(int a, int b){
return(a < b ? a : b);
}
void manacher(int lin)
{
int c = 0, dr = 0, j;
for(j=1; j<=m; ++j)
{
if(dr < j) man[lin][j] = 0;
else man[lin][j] = minim(dr-j, man[lin][2*c-j]);
while(j+man[lin][j]+1 <= m && j-man[lin][j]-1 > 0 && v[lin][j+man[lin][j]+1] == v[lin][j-man[lin][j]-1])
man[lin][j]++;
if(j + man[lin][j] > dr)
{
dr = j + man[lin][j];
c = j;
}
}
for(j=1; j<=m; ++j)
man[lin][j] = man[lin][j] * 2 + 1;
}
int main()
{
freopen("dreptpal.in", "r", stdin);
freopen("dreptpal.out", "w", stdout);
int i, j, k = 0, ans = 0;
scanf("%d%d", &n, &m);
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
scanf("%d", &v[i][j]);
for(i=1; i<=n; ++i)
manacher(i);
for(j=1; j<=m; ++j)
{
k = 0;
st[++k] = left[1][j] = 1;
for(i=2; i<=n; ++i){
while(k > 0 && man[st[k]][j] >= man[i][j])
left[i][j] += left[st[k--]][j];
st[++k] = i;
left[i][j]++;
}
k = 0;
st[++k] = n;
right[n][j] = 1;
for(i=n-1; i>=1; --i){
while(k > 0 && man[st[k]][j] >= man[i][j])
right[i][j] += right[st[k--]][j];
st[++k] = i;
right[i][j]++;
}
}
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
if((left[i][j] + right[i][j] - 1) * man[i][j] > ans)
ans = (left[i][j] + right[i][j] - 1) * man[i][j];
printf("%d", ans);
return 0;
}