Cod sursa(job #2016448)

Utilizator robx12lnLinca Robert robx12ln Data 29 august 2017 14:11:04
Problema DreptPal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include<fstream>
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int Long_pal[1005][1005], a[1005][1005], C, R, n, m, st[2][1005], sol;
int main(){
    fin >> n >> m;
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= m; j++ ){
            fin >> a[i][j];
        }
        a[i][0] = -1;
        a[i][m + 1] = -2;
    }
    for( int i = 1; i <= n; i++ ){
        C = R = 0;
        for( int j = 1; j <= m; j++ ){
            int mirr_poz = C * 2 - j;
            Long_pal[i][j] = 1;
            if( j <= R )
                Long_pal[i][j] = min( Long_pal[i][mirr_poz], R - j + 1 );
            while( a[i][ j - (Long_pal[i][j] / 2) - 1 ] == a[i][ j + (Long_pal[i][j] / 2) + 1 ] )
                Long_pal[i][j] += 2;
            if( j + Long_pal[i][j] / 2 > R ){
                C = j;
                R = j + Long_pal[i][j] / 2;
            }
        }
    }
    sol = 0;
    for( int j = 1; j <= m; j++ ){
        int maxim = 0;
        int k = 0;
        for( int i = 1; i <= n; i++ ){
            if( Long_pal[i][j] > st[0][k] ){
                st[0][++k] = Long_pal[i][j];
                st[1][k] = i;
            }else{
                int poz = 0;
                while( st[0][k] >= Long_pal[i][j] && k > 0 ){
                    if( maxim < st[0][k] * ( i - st[1][k] ) )
                        maxim = st[0][k] * ( i - st[1][k] );
                    poz = st[1][k];
                    k--;
                }
                if( Long_pal[i][j] > 0 ){
                    st[0][++k] = Long_pal[i][j];
                    st[1][k] = poz;
                }
            }
        }
        while( k > 0 ){
            if( maxim < st[0][k] * ( n + 1 - st[1][k] ) )
                maxim = st[0][k] * ( n + 1 - st[1][k] );
            k--;
        }
        sol = max( sol, maxim );
    }
    fout << sol << "\n";
    return 0;
}