Cod sursa(job #637416)

Utilizator LgregL Greg Lgreg Data 20 noiembrie 2011 14:21:20
Problema DreptPal Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 1.87 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int lung[101010];
int v[101010],N,st,dr,q;
int mat[1010][1010];
int globj;
int make_pal()
{
for(int i=1;i<=N;++i)
    lung[i]=0;

 lung[1]=0;
    st=1;
    dr=1;
    for(int i=2;i<=N;++i)
    {
     //   printf("%d",v[i]);
            if(i<=dr)
            {
            int q=st+dr-i;
            lung[i]=min(lung[q],dr-i);

            if(i+lung[i]==dr)
            {
                st=i-lung[i];
                dr=i+lung[i];
                while(dr<N&&st>1&&v[i-lung[i]-1]==v[i+lung[i]+1])
                    {
                    ++lung[i];
                    --st;
                    ++dr;
                    }
            }
            }
            else
            {

                st=dr=i;
                lung[i]=0;
                while(st>1&&dr<N&&v[i-lung[i]-1]==v[i+lung[i]+1])
                {
                    --st;
                    ++dr;
                    ++lung[i];
                }
            }

    }
    for(int i=1;i<=N;++i)
    {
      mat[i][globj]=lung[i];
    }
   //printf("\n");
}
int stiv[1010];
int nrs[1010];
int k=0;
int rez=0;
int M;
int main()
{
freopen("dreptpal.in","r",stdin);
freopen("dreptpal.out","w",stdout);

scanf("%d%d",&M,&N);
for(int j=1;j<=M;++j)
{globj=j;
for(int i=1;i<=N;++i)
{
    scanf("%d",&v[i]);
}
 make_pal();
}
    for(int i=1;i<=N;++i)
    {
        k=0;
        for(int j=1;j<=M+1;++j)
            {int number=0;
                while(stiv[k]>=mat[i][j]&&k!=0)
                    {
                    number+=nrs[k];
                    rez=max(rez,(stiv[k]*2+1)*number);
                    --k;
                    }
                stiv[++k]=mat[i][j];
                nrs[k]=number+1;
            }
        //printf("\n");
    }
    printf("%d\n",rez);
}