Cod sursa(job #1956415)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 6 aprilie 2017 18:51:38
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>
using namespace std;

fstream in ( "dreptpal.in" , ios::in  );
fstream out( "dreptpal.out", ios::out );

const int DIM = 1e3 + 5;

vector<int> stk;

int arr[DIM][DIM], psl[DIM];
int len[DIM][DIM], psr[DIM];

int main( void ) {
    
    int n, m;
    in >> n >> m;
    
    for( int i = 1; i <= n; i ++ ) {
        for( int j = 1; j <= m; j ++ )
            in >> arr[i][j];
        
        for( int j = 1, le = 0, ri = 0, md = 0; j <= m; j ++ ) {
            if( j > ri ) {
                len[i][j] = 1;
                
                le = ri = md = j;
                while( le > 1 && ri < m && arr[i][le - 1] == arr[i][ri + 1] ) {
                    len[i][j] ++;
                    le --; ri ++;
                }
            }
            else {
                int ps = md - ( j - md );
                
                if( ps - len[i][ps] < le ) {
                    len[i][j] = ri - j + 1;
                    
                    le = j - len[i][j] + 1; ri = ri; md = j;
                    while( le > 1 && ri < m && arr[i][le - 1] == arr[i][ri + 1] ) {
                        len[i][j] ++;
                        le --; ri ++;
                    }
                }
                else
                    len[i][j] = len[i][ps];
            }
        }
    }
    
    int ans = 0;
    for( int j = 1; j <= m; j ++ ) {
        
        stk.assign( 1, 0 );
        for( int i = 1; i <= n; i ++ ) {
            while( len[stk.back()][j] >= len[i][j] )
                stk.pop_back();
            
            psl[i] = stk.back();
            stk.push_back( i );
        }
        
        stk.assign( 1, n + 1 );
        for( int i = n; i >= 1; i -- ) {
            while( len[stk.back()][j] >= len[i][j] )
                stk.pop_back();
            
            psr[i] = stk.back();
            stk.push_back( i );
        }
        
        for( int i = 1; i <= n; i ++ )
            ans = max( ans, ( psr[i] - psl[i] - 1 ) * ( 2 * len[i][j] - 1 ) );
    }
    
    out << ans << endl;
    return 0;
}