Cod sursa(job #637484)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 20 noiembrie 2011 14:42:54
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 3.32 kb
#include<stdio.h>
#include<assert.h>
#include<algorithm>
using namespace std;

int n,m,sol,st1[1002],st2[1002],li[1002],ri[1002],p[1011][1020],a[1051][1051];

void read()
{
    assert(freopen("dreptpal.in","r",stdin)!=NULL);
    scanf("%d%d",&n,&m);
    int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            scanf("%d",&a[i][j]);
    for(i=1;i<=n;++i)
    {
        a[i][0]=2000000000;
        a[i][m+1]=2000000001;
    }
}

void do_smen()
{
    int st,dr,i,j,lim,last,lc;
    lim=2*m-1;
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=lim;++j)
        {
            if(j==1)
            {
                p[i][j]=1;
                lc=1;
                last=1;
            }
            else
            {
                if(j%2==0)
                {
                    if(last*2-2<=j)
                        p[i][j]=p[i][lc*2-j];
                    st=j/2-p[i][j]/2;
                    dr=j/2+1+p[i][j]/2;
                    while(st>0 && dr<=m && a[i][st]==a[i][dr])
                    {
                        p[i][j]+=2;
                        st--;
                        dr++;
                    }
                    st++;
                    dr--;
                    if(dr>last)
                    {
                        last=dr;
                        lc=j;
                    }
                }
                else
                {
                    p[i][j]=1;
                    if(last*2-1<=j)
                        p[i][j]=max(p[i][lc*2-j],1);
                    st=j/2-(p[i][j]+1)/2;
                    dr=j/2+(p[i][j]+1)/2;
                    while(st>0 && dr<=m && a[i][st]==a[i][dr])
                    {
                        p[i][j]+=2;
                        st--;
                        dr++;
                    }
                    dr--;
                    st++;
                    if(dr>last)
                    {
                        last=dr;
                        lc=j;
                    }
                }
            }
        }
    }
}

void solve()
{
    do_smen();
    //printf("\n");
    int i,j;
    for(i=1;i<=m;++i)
    {
        for(j=1;j<=n;++j)
        {
            while(st1[0] && p[st1[st1[0]]][i*2-1]>=p[j][i*2-1])
                {
                    st1[st1[0]]=0;
                    --st1[0];
                }
            li[j]=j-st1[st1[0]];
            st1[++st1[0]]=j;
        }
        for(j=n;j>0;--j)
        {
            while(st2[0] && p[st2[st2[0]]][i*2-1]>=p[j][i*2-1])
            {
                st2[st2[0]]=0;
                --st2[0];
            }
            if(st2[0]==0)
                ri[j]=n-j+1;
            else
                ri[j]=st2[st2[0]]-j;
            st2[++st2[0]]=j;
        }
        for(j=1;j<=n;++j)
        {
            sol=max(sol,p[j][i*2-1]*(ri[j]+li[j]-1));
            //printf("%d ",li[j]);
        }
        //printf("\n");
        //for(j=1;j<=n;++j)
        //{
           // printf("%d ",ri[j]);
       // }
        //printf("\n\n");
        while(st2[0])
        {
            st2[st2[0]]=0;
            --st2[0];
        }
        while(st1[0])
        {
            st1[st1[0]]=0;
            --st1[0];
        }
    }
}

void write()
{
    assert(freopen("dreptpal.out","w",stdout)!=NULL);
    printf("%d",sol);
}

int main()
{
    //assert(freopen("dreptpal.out","w",stdout)!=NULL);
    read();
    solve();
    write();
    return 0;
}