Cod sursa(job #637564)

Utilizator Fetita_JucausaFetita Buclucasa Fetita_Jucausa Data 20 noiembrie 2011 15:13:50
Problema DreptPal Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 1.68 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=2; j<=M; ++j)
            if (j>dr)
            {
                st=dr=j;
                for ( ; v[i][st-1]==v[i][dr+1] && st>1 && dr<M; --st, ++dr)
                    ++l[i][j];
            }
            else
            {
                l[i][j]=min (l[i][st+dr-j],dr-j);
                if (j+l[i][j]==dr)
                {
                    st=j-l[i][j];
                    dr=j+l[i][j];
                    for ( ; v[i][st-1]==v[i][dr+1] && st>1 && dr<M; --st, ++dr)
                        ++l[i][j];
                }
            }
    }

    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]<<1)|1)*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]<<1)|1)*nr);
            --vf;
        }
    }

    printf ("%d",bst_sol);
}

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

    read ();
    solve ();

    return 0;
}