Cod sursa(job #1316401)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 13 ianuarie 2015 19:52:23
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<fstream>

using namespace std;

ifstream fin( "dreptpal.in" );
ofstream fout( "dreptpal.out" );

const int nmax = 1000;
const int inf = 1 << 30;
int m, st[ nmax + 1 ], dr[ nmax + 1 ];
int a[ nmax + 1 ][ nmax + 1 ];
int p[ nmax + 2 ][ nmax + 1 ];

void extend( int i, int j ) {
    while ( j - p[ i ][ j ] >= 0 && j + p[ i ][ j ] <= m && a[ i ][ j - p[i][j] ] == a[ i ][ j + p[i][j] ] ) {
        ++ p[ i ][ j ];
    }
}
int main() {
    int n, c;
    fin >> n >> m;
    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= m; ++ j ) {
            fin >> a[ i ][ j ];
        }
    }
    for( int i = 1; i <= n; ++ i ) {
        c = 1;
        for( int j = 1; j <= m; ++ j ) {
            if ( j > c + p[ i ][ c ] ) {
                c = j;
                extend( i, j );
            } else {
                int x = 2 * c - j;
                if ( x - p[ i ][ x ] > c - p[ i ][ c ] ) {
                    p[ i ][ j ] = p[ i ][ x ];
                } else {
                    p[ i ][ j ] = x - ( c - p[ i ][ c ] );
                    extend( i, j );
                }

                if ( j + p[ i ][ j ] > c + p[ i ][ c ] ) {
                    c = j;
                }
            }
        }
    }
    int ans = 0;
    for( int j = 1; j <= m; ++ j ) {
        p[ 0 ][ j ] = -inf;
        for( int i = 1; i <= n; ++ i ) {
            int k = i - 1;
            while ( p[ k ][ j ] >= p[ i ][ j ] ) {
                k = st[ k ];
            }
            st[ i ] = k;
        }
        p[ n + 1 ][ j ] = -inf;
        for( int i = n; i > 0; -- i ) {
            int k = i + 1;
            while ( p[ k ][ j ] >= p[ i ][ j ] ) {
                k = dr[ k ];
            }
            dr[ i ] = k;

            if ( ans < (dr[ i ] - st[ i ] - 1) * (2 * p[ i ][ j ] - 1) ) {
                ans = (dr[ i ] - st[ i ] - 1) * (2 * p[ i ][ j ] - 1);
            }
        }
    }
    fout << ans << "\n";
    fin.close();
    fout.close();
    return 0;
}