Cod sursa(job #1346637)

Utilizator ade_tomiEnache Adelina ade_tomi Data 18 februarie 2015 14:48:59
Problema DreptPal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>
int p[1005][1005],a[1005][1005],i,j,n,m,k,sus[1005],jos[1005],st[1005],nr,sol;
void extinde (int q)
{
    while(q+p[i][q]+1<=m&&q-p[i][q]-1>0&&a[i][q+p[i][q]+1]==a[i][q-p[i][q]-1])
        p[i][q]++;
}
int max(int a, int b)
{

    if(a>b)
        return a;
    return b;
}
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",&a[i][j]);
    for(i=1;i<=n;i++)
    {

        p[i][1]=0;
        k=1;
        for(j=2;j<=m;j++)
        {

            if(p[i][k]+k<j)
                extinde(j);
            else
            {

                if(p[i][k]+k<=j+p[i][2*k-j])
                {

                    p[i][j]=p[i][2*k-j];
                    extinde(j);
                }
                else
                    p[i][j]=p[i][2*k-j];
            }
        }
    }/*
    for(i=1;i<=n;i++)
    {

        for(j=1;j<=m;j++)
            printf("%d ",p[i][j]);
        printf("\n");
    }
*/
    for(j=1;j<=m;j++)
    {

        nr=0;
        st[0]=0;
        for(i=1;i<=n;i++)
        {

            while(nr>0&&p[st[i]][j]>=p[i][j])
                nr--;
            sus[i]=st[nr];
            nr++;
            st[nr]=i;

        }
        nr=0;
        st[0]=n+1;
        for(i=n;i>=1;i--)
        {

            while(nr>0&&p[st[i]][j]>=p[i][j])
                nr--;
            jos[i]=st[nr];
            nr++;
            st[nr]=i;

        }
        for(i=1;i<=n;i++)
            sol=max(sol,(jos[i]-sus[i]-1)*(p[i][j]*2+1));
    }
    printf("%d",sol);

    return 0;
}