Cod sursa(job #790463)

Utilizator veleanduAlex Velea veleandu Data 21 septembrie 2012 14:25:56
Problema DreptPal Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <cstdio>
using namespace std; 
#define maxn 1000
#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;
        }
    }

    // facem chestia aia pe coloane
    long Maxim=0;
    long St,Dr,Lung,Col;

    for ( j=1; j<=m; j++ )
    {
        for ( i=1; i<=n; i++ )
            De[i]=0;
        De[0]=0;
        Ps[0][j]=-1;
        last=0;
        for ( i=1; i<=n; i++ )
        {
            while ( Ps[i][j] <= Ps[ De[last]  ][j] )
                last--;
            if ( De[last]==0 )
            {
                // minimul e curent
                if ( Maxim < ( i*(2*Ps[i][j]+1) ) )
                {
                    Maxim = i*(2*Ps[i][j]+1);
                    St=1;
                    Dr=i;
                    Lung=(2*Ps[i][j]+1);
                    Col=j;
                }
            }
            else{
                if ( Maxim < ( i-De[last] ) * ( 2*Ps[i][j]+1 ) )
                {
                    Maxim= ( i-De[last] ) * ( 2*Ps[i][j]+1 );
                    St=De[last]+1;
                    Dr=i;
                    Lung=( 2*Ps[i][j]+1 );
                    Col=j;
                }
            }
            last++;
            De[last]=i;
        }
    }
/*    printf("%d %d %d %d\n\n", Col,St,Dr,Lung);
    for ( i=1; i<=n; i++,printf("\n") )
        for ( j=1; j<=m; j++ )
            printf("%d ", Ps[i][j] );*/
    printf("%d\n", Maxim );
    return 0;
}