Cod sursa(job #1757051)

Utilizator silkMarin Dragos silk Data 14 septembrie 2016 11:52:24
Problema DreptPal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <cstdio>
#include <cstring>
#define NMax 1002
#define MIN(a,b)((a)<(b)?(a):(b))

int P[NMax+1][NMax+1];
int a[NMax+1][NMax+1];
int stack[NMax+1];
int r[NMax+1];
int l[NMax+1];

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

    int N,M,i,j,R,C,jj,vf,ans=0;

    scanf("%d %d",&N,&M);
    for(i = 1; i <= N; ++i)
        for(j = 1; j <= M; ++j) scanf("%d",&a[i][j]);

    for(i = 1; i <= N; ++i) a[i][0] = -1;
    for(i = 1; i <= N; ++i) a[i][M+1] = -2;

    for(i = 1; i <= N; ++i)
    {
        for(R = C = 0, j = 1; j <= M; ++j)
        {
            jj = 2*C-j;
            P[i][j] = ( R>j? MIN( P[i][jj], R-j ) : 0 );
            while( a[i][j+P[i][j]+1] == a[i][j-P[i][j]-1] ) ++P[i][j];

            if( R < P[i][j] + j )
            {
                C = j;
                R = P[i][j] + j;
            }

            P[i][j] = 2*P[i][j]+1;
        }
    }

    for(j = 1; j <= M; ++j)
    {
        memset(l, 0, sizeof(l) );
        memset(r, 0, sizeof(r) );

        stack[0] = 0;
        for(vf = 0, i = 1; i <= N; ++i)
        {
            while( vf>0 && P[ stack[vf] ][j] >= P[i][j] ) --vf;
            l[i] = stack[vf]+1;
            stack[++vf] = i;
        }

        stack[0] = N+1;
        for(vf = 0, i = N; i >= 1; --i)
        {
            while( vf>0 && P[ stack[vf] ][j] >= P[i][j] ) --vf;
            r[i] = stack[vf]-1;
            stack[++vf] = i;
        }

        for(i = 1; i <= N; ++i)
        if( P[i][j] * ( r[i] - l[i] + 1 ) > ans ) ans = P[i][j] * ( r[i] - l[i] + 1 );
    }

    printf("%d\n",ans);



return 0;
}