Cod sursa(job #637498)

Utilizator Fetita_JucausaFetita Buclucasa Fetita_Jucausa Data 20 noiembrie 2011 14:50:57
Problema DreptPal Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 1.69 kb
#include <algorithm>
#include <cstdio>
using namespace std;

#define DIM 1005

int v[DIM][DIM],l[DIM][2*DIM];
int st_val[DIM],st_nr[DIM];
int N,M,bst_sol;

void read ()
{
    scanf ("%d%d",&N,&M);
    for (int i=1; i<=N; ++i)
        for (int j=1; j<=M; ++j)
            scanf ("%d",&v[i][j]);
}

void solve ()
{
    for (int i=1; i<=N; ++i)
    {
        int st=1,dr=1;
        for (int j=1; j<=M; ++j)
        {
            if (dr>j)
                l[i][j]=min (l[i][(st<<1)-j],dr-i+1);
            for (int fs=j-l[i][j], ls=j+l[i][j]; fs>=1 && ls<=M; )
            {
                if (j+l[i][j]-1>dr)
                {
                    st=j;
                    dr=j+l[i][j]-1;
                }
                if (v[i][fs]==v[i][ls])
                {
                    ++l[i][j];
                    --fs; ++ls;
                }
                else
                    break ;
            }
            l[i][j]=(l[i][j]<<1)-1;
        }
    }

    /*for (int j=1; j<=M; ++j)
    {
        int vf=0;
        for (int i=1; i<=N; ++i)
        {
            int nr=0;
            while (vf && l[i][j]<=st_val[vf])
            {
                nr+=st_nr[vf];
                bst_sol=max (bst_sol,st_val[vf]*nr);
                --vf;
            }
            st_val[++vf]=l[i][j]; st_nr[vf]=++nr;
        }
        int nr=0;
        while (vf)
        {
            nr+=st_nr[vf];
            bst_sol=max (bst_sol,st_val[vf]*nr);
            --vf;
        }
    }*/

    printf ("%d",bst_sol);
}

int main ()
{
    freopen ("dreptpal.in","r",stdin);
    freopen ("dreptpal.out","w",stdout);

    read ();
    solve ();

    return 0;
}