Cod sursa(job #1297122)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 21 decembrie 2014 18:21:17
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define N 1003
int a[N][N],b[N][N];
int i , j , n , m ,r,l, c,mirror,sol;
int st[N],h;

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

    scanf("%d %d\n",&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){
        r = c = 0;
        for(j=1;j<=m-1;++j){
            mirror = 2 * c - j;
            b[i][j] = r > j ? min( b[i][mirror] , r -j ) : 0;
            while( j - b[i][j]-1 > 0 &&  a[i][ j - b[i][j]-1 ] == a[i][ j+ b[i][j]+1  ] )
                ++b[i][j];

            if( r < j + b[i][j] ){
                r = j + b[i][j];
                c = j;
            }
        }
    }
    for(j=3;j<=m;++j){
        for(i=1;i<=n+1;++i){
            while( h && b[i][j] <= b[ st[h] ][j] ){
               --h;
               l = h ? st[h]+1 : 1;
               r = i - 1;
               sol = max( sol , (r-l+1) * ( 2 * b[ st[h+1] ][j] + 1 )  );
            }
            st[++h]=i;
        }
        h = 0;
    }
    printf("%d",sol);

    return 0;
}