Cod sursa(job #638005)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 20 noiembrie 2011 18:07:07
Problema DreptPal Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 4.69 kb
#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<algorithm>
using namespace std;

int n,m,sol,meniu,st1[1012],st2[1012],li[1012],ri[1012],v[1010];
char pars[30000];
int p[1011][1020];

void do_smen(int x);

void read()
{
    assert(freopen("dreptpal.in","r",stdin)!=NULL);
    scanf("%d%d\n",&n,&m);
    int i,j,u,h;
    int d;
    for(i=1;i<=n;++i)
    {
        j=1;
        gets(pars);
        u=strlen(pars);
        h=0;
        d=0;
        while(h<u)
        {
            if(pars[h]==' ')
            {
                v[j]=d;
                //assert(v[j]!=0);
                ++j;
                d=0;
                ++h;
                continue;
            }
            d*=10;
            d+=pars[h]-'0';
            ++h;
        }
        v[j]=d;
        do_smen(i);
    }
    /*for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            scanf("%d",&a[i][j]);*/
}

/*inline short int maxx(short int x, short int y)
{
    if(x>y)
        return x;
    return y;
}*/

void do_smen(int x)
{
    int st,dr,j,last,lc;
    for(j=1;j<=m;++j)
    {
        if(j==1)
        {
            p[x][j]=1;
            lc=1;
            last=1;
        }
        else
        {
            p[x][j]=1;
            if(last>=j)
                p[x][j]=max(1,p[x][lc*2-j]);
            st=j-(p[x][j]+1)/2;
            dr=j+(1+p[x][j])/2;
            while(st>0 && dr<=m && v[st]==v[dr])
            {
                p[x][j]+=2;
                ++dr;
                --st;
            }
            ++st;
            --dr;
            if(dr>last)
            {
                lc=j;
                last=dr;
            }
        }
    }
}
/*
void do_smen(int x)
{
    short int st,dr,j,lim,last,lc;
    lim=2*m-1;
        for(j=1;j<=lim;++j)
        {
            if(j==1)
            {
                p[j][x]=1;
                lc=1;
                last=1;
            }
            else
            {
                if(!(j&1))
                {
                    if(last*2-2<=j)
                        p[i][j]=p[i][lc*2-j];
                    st=(j>>1)-(p[i][j]>>1);
                    dr=(j>>1)+1+(p[i][j]>>1);
                    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[j][x]=1;
                if(last*2-1<=j)
                    p[j][x]=max(p[lc*2-j][x],1);
                st=(j>>1)-((p[j][x]+1)>>1);
                dr=(j>>1)+((p[j][x]+1)>>1);
                while(st>0 && dr<=m && v[st]==v[dr])
                {
                    p[j][x]+=2;
                    --st;
                    ++dr;
                }
                --dr;
                ++st;
                if(dr>last)
                {
                    last=dr;
                    lc=j;
                }
            }
        }
    }
}*/

void solve()
{
    int i,j;
    for(i=1;i<=m;++i)
    {
        for(j=1;j<=n;++j)
        {
            while(st1[0] && p[st1[st1[0]]][i]>=p[j][i])
                {
                    --st1[0];
                }
            li[j]=j-st1[st1[0]]-1;
            st1[++st1[0]]=j;
        }
        for(j=n;j>0;--j)
        {
            while(st2[0] && p[st2[st2[0]]][i]>=p[j][i])
            {
                --st2[0];
            }
            if(st2[0]==0)
                ri[j]=n-j;
            else
                ri[j]=st2[st2[0]]-j-1;
            st2[++st2[0]]=j;
        }
        for(j=1;j<=n;++j)
            sol=max(sol,p[j][i]*(ri[j]+li[j]+1));
        st2[0]=0;
        st1[0]=0;
    }
    meniu=sol;
    assert(meniu>=125*n);
    if(meniu<n)
        meniu=n;
}


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

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

int main()
{
    read();
    solve();
    write();
    return 0;
}