Cod sursa(job #1472336)

Utilizator enedumitruene dumitru enedumitru Data 16 august 2015 23:47:44
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<fstream>
#define Nmax 1005
using namespace std;
ifstream f("dreptpal.in"); ofstream g("dreptpal.out");
int n,m,i,j,p,u,arie,best,vf;
int A[Nmax][Nmax],D[Nmax][Nmax],St[Nmax];
int main()
{   f>>n>>m;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j) f>>A[i][j];
    for(i=1;i<=n;++i)
    {   p=u=1;
        for(j=1;j<=m;++j)
            if(j<=u )
            {   D[i][j]=D[i][p+u-j]<u-j ? D[i][p+u-j] : u-j;
                if(j+D[i][j]>=u)
                {   p=j-D[i][j]; u=j+D[i][j];
                    while(p>=2 && u<=m-1 && A[i][p-1]==A[i][u+1]){--p; ++u; ++D[i][j];}
                }
            }
            else
            {   p=u=j;
                while(p>=2 && u<=m-1 && A[i][p-1]==A[i][u+1]) {--p; ++u; ++D[i][j];}
            }
        for(j=1;j<=m;++j ) D[i][j]=D[i][j]+D[i][j]+1;
    }
    for(j=1;j<=m;++j)
    {   for(vf=0,i=1;i<=n;++i)
        {   p=St[vf];
            while(vf && D[i][j]<D[St[vf]][j])
            {   arie=D[St[vf]][j]*(p-St[vf-1]);
                if(best<arie) best=arie;
                --vf;
            }
            St[++vf]=i;
        }
        for(p=St[vf];vf;--vf )
        {   arie=D[St[vf]][j]*( p-St[vf-1]);
            if(best<arie ) best=arie;
        }
    }
    g<<best<<"\n"; g.close(); return 0;
}