Pagini recente » Cod sursa (job #1071175) | Cod sursa (job #604298) | Cod sursa (job #2865556) | Cod sursa (job #1231695) | Cod sursa (job #637423)
Cod sursa(job #637423)
#include <cstdio>
#define Nmax 1001
int N, M, i, j, st;
int A[Nmax][Nmax], L[Nmax][Nmax];
int A1[Nmax], A2[Nmax], S[Nmax];
int best;
char SS[10000];
int palind(int x, int y)
{
int st, dr;
st = dr = x;
while (st>=0 && dr<M)
{
if (A[y][st] != A[y][dr]) break;
--st; ++dr;
}
return dr-st-1;
}
int main()
{
freopen("dreptpal.in","r",stdin);
freopen("dreptpal.out","w",stdout);
scanf("%d %d", &N, &M);
for (i=0; i<N; ++i)
{
fgets(SS, 10000, stdin);
int k=0;
for (j=0; j<M; ++j)
{
while (SS[k] != ' ')
{
A[i][j] = (A[i][j] * 10) + SS[k] - '0';
++k;
}
++k;
}
}
for (i=0; i<M; ++i)
if ((M-i) * N < best) break;
else
{
for (j=0; j<N; ++j)
{
L[i][j] = palind(i, j);
if (L[i][j] > best) best = L[i][j];
}
//stanga
for (j=0; j<N; ++j)
{
A1[j] = L[i][0];
while (L[i][S[st]] >= L[i][j] && st>=0)
--st;
if (st>=0 && L[i][j] * (j - S[st]) > A1[j]) A1[j] = L[i][j] * (j - S[st]);
if (st<0 && L[i][j] * (j + 1) > A1[j]) A1[j] = L[i][j] * (j + 1);
S[++st] = j;
}
//dreapta
for (j=N-1; j>=0; --j)
{
A2[j] = L[i][j];
while (L[i][S[st]] >= L[i][j] && st>=0)
--st;
if (st>=0 && L[i][j] * (S[st] - j) > A2[j]) A2[j] = L[i][j] * (S[st] - j);
if (st<0 && L[i][j] * (N - j) > A2[j]) A2[j] = L[i][j] * (N - j);
S[++st] = j;
}
//total
for (j=0; j<N; ++j)
if (A1[j] + A2[j] - L[i][j] > best) best = A1[j] + A2[j] - L[i][j];
}
printf("%d\n", best);
return 0;
}