Cod sursa(job #801429)

Utilizator veleanduAlex Velea veleandu Data 24 octombrie 2012 12:13:47
Problema DreptPal Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <iostream>

using namespace std; 
#define maxn 1005
#define min(a,b) ((a<b)?(a):(b))

    long i,j;
    long n,m;
    long Ps[maxn][maxn];
    long T[maxn][maxn];
    long last;
    long De[maxn];

int main()
{
    freopen ("dreptpal.in","r",stdin);
    freopen ("dreptpal.out","w",stdout);

    scanf ("%d %d", &n, &m );
    for ( i=1; i<=n; i++ )
        for ( j=1; j<=m; j++ )
            scanf ("%d", &T[i][j]);

    // facem pscpld
    for ( i=1; i<=n; i++ )
    {
        last=0;
        for ( j=1; j<=m; j++ )
        {
            if ( last+Ps[i][last] >= j )
                Ps[i][j]=min ( last+Ps[i][last]-j ,  Ps[i][2*last-j] );
            while (  ( j-Ps[i][j]-1 >=1 ) &&
                     ( j+Ps[i][j]+1 <=m ) &&
                     ( T[i][ j+Ps[i][j]+1 ] == T[i][ j-Ps[i][j]-1 ] ) )
                Ps[i][j]++;
            if ( last+Ps[i][last] < j+Ps[i][j] )
                last=j;
        }
    }
    for ( i=1; i<=n; i++ )
        for ( j=1; j<=m; Ps[i][j]<<=1,Ps[i][j]++,j++ )
            ;
    // facem chestia aia pe coloane
    long Maxim=0;
    long lf[maxn],rg[maxn];

    for ( j=1; j<=m; j++ )
    {
        last=0;
        De[0]=0;
        Ps[0][j]=-1;
        for ( i=1; i<=n; i++ )
        {
            while ( Ps[i][j]<= Ps[ De[last] ][j] )
                last--;
            lf[i]=i-De[last];
            De[++last]=i;
        }
        last=0;
        for ( i=n; i>0; i-- )
        {
            while ( Ps[i][j]<=Ps[ De[last] ][j] )
                last--;
            if ( last )
                rg[i]=De[last]-i;
            else    
                rg[i]=n-i+1;
            De[++last]=i;
        }
        for ( i=1; i<=n; i++ )
            if ( Maxim < (rg[i]-lf[i]+1)*Ps[i][j] )
                Maxim=(rg[i]-lf[i]+1)*Ps[i][j];
    }
    printf("%d\n", Maxim );
    return 0;
}