Cod sursa(job #1005856)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 5 octombrie 2013 22:33:41
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<stdio.h>
unsigned a[1005][1005],pa[1005][1005],v[1005],st[1005],dr[1005],s[1005];
int main()
{
    freopen("dreptpal.in","r",stdin);
    freopen("dreptpal.out","w",stdout);
    unsigned n,m,i,j,sp=0,p,l;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%u",&a[i][j]);
            s[j]=a[i][j];
        }
            p=0;
    for(j=1;j<=m;j++)
    {
    if(j>pa[i][p]+p)
    {
        for(pa[i][j]=1;pa[i][j]<j && s[j+pa[i][j]]==s[j-pa[i][j]] && j-pa[i][j]>0 && j+pa[i][j]<=m;pa[i][j]++);
        p=j;
    }
    else
{
    if(2*p-j-pa[i][2*p-j]>p-pa[i][p])
    pa[i][j]=pa[i][2*p-j];
    else
    pa[i][j]=p+pa[i][p]-j;
    if(j+pa[i][j]==p+pa[i][p])
    {
        for(;s[j-pa[i][j]]==s[j+pa[i][j]] && j+pa[i][j]<=m && j-pa[i][j]>0;pa[i][j]++);
        p=j;
    }
}
    }
    for(j=1;j<=m;j++)
        pa[i][j]--;
    }
    for(j=1;j<=m;j++)
    {
        l=0;
        v[l]=0;
        for(i=1;i<=n;i++)
        {
            while(l!=0 && pa[i][j]<=pa[v[l]][j])
                l--;
            st[i]=v[l]+1;
            l++;
            v[l]=i;
        }
        l=0;
        v[l]=n+1;
        for(i=n;i>=1;i--)
        {
            while(l!=0 && pa[i][j]<=pa[v[l]][j])
                l--;
            dr[i]=v[l]-1;
            l++;
            v[l]=i;
        }
        for(i=1;i<=n;i++)
        {
            if(sp<(dr[i]-st[i]+1)*(pa[i][j]*2+1))
                sp=(dr[i]-st[i]+1)*(pa[i][j]*2+1);
        }
    }
    printf("%u\n",sp);
    return 0;
}