Cod sursa(job #1314543)

Utilizator heracleRadu Muntean heracle Data 11 ianuarie 2015 23:05:04
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <cstdio>

FILE* in=fopen("dreptpal.in","r");
FILE* out=fopen("dreptpal.out","w");

const int Q=1005;

int l,c;

int v[Q][Q];

int man[Q][Q];

int up[Q][Q];
int dw[Q][Q];

int min(int a, int b)
{
    return a<b?a:b;
}

int stv[Q],s;

int main()
{
    fscanf(in,"%d%d",&l,&c);


    for(int i=1; i<=l; i++)
    {
        v[i][0]=-1;
        for(int j=1; j<=c; j++)
        {
            fscanf(in,"%d",&v[i][j]);
        }
        v[i][c+1]=-2;
    }


    for(int i=1; i<=l; i++)
    {
        int mid=0,right=0;

        for(int j=1; j<=c; j++)
        {
            if(j<right)
                man[i][j]=min(man[i][2*mid-j],right);

            while(v[i][j-man[i][j]-1]==v[i][j+man[i][j]+1])
                man[i][j]++;

            if(j+man[i][j]>right)
            {
                mid=j;
                right=j+man[i][j];
            }
        }
    }

    for(int j=1; j<=c; j++)
    {
        s=0;
        for(int i=1; i<=l; i++)
        {
            while(s && man[stv[s]][j]>man[i][j])
            {
                up[stv[s]][j]=i-1;
                s--;
            }
            stv[++s]=i;
        }

        while(s)
        {
            up[stv[s]][j]=l;
            s--;
        }

        //down

        for(int i=l; i>0; i--)
        {
            while(s && man[stv[s]][j]>man[i][j])
            {
                dw[stv[s]][j]=i+1;
                s--;
            }
            stv[++s]=i;
        }
        while(s)
        {
            dw[stv[s]][j]=1;
            s--;
        }
    }

    int rez=0;

    for(int i=1; i<=l; i++)
    {
        for(int j=1; j<=c; j++)
        {
            if((up[i][j]-dw[i][j]+1)*(man[i][j]*2+1)>rez)
                rez=(up[i][j]-dw[i][j]+1)*(man[i][j]*2+1);
        }
    }

    fprintf(out,"%d",rez);

    return 0;
}