Cod sursa(job #1316351)

Utilizator xtreme77Patrick Sava xtreme77 Data 13 ianuarie 2015 19:14:00
Problema DreptPal Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
/*
 * Code by Spiromanul
 */


#include <fstream>
#include <cstring>
#include <stack>

const char IN [ ] = "dreptpal.in" ;
const char OUT [ ] = "dreptpal.out" ;
const int MAX = 1111 ;

// #solutia e defapt o dragalasenie

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

int mat [ MAX ] [ MAX ] ;

int pali [ MAX ] ;

inline void do_the_job ( int *v , int m )
{
    memset ( pali , 0 , sizeof ( pali ) ) ;
    int centru = 1 ;
    int R = 1 ;
    pali [ 1 ] = 1 ;
    for ( int i = 2 ; i < m ; ++ i )
    {
        pali [ i ] = ( ( R > i ) ? ( min ( pali [ 2 * centru - i ] , R - i ) ) : 0 ) ;
        while ( i - pali [ i ] - 1 >= 1 and i + pali [ i ] + 1 <= m and v [ i - pali [ i ] - 1 ] == v [ i + pali [ i ] + 1 ] )
            pali [ i ] ++ ;

        if ( i + pali [ i ] > R )
        {
            R = i + pali [ i ] ;
            centru = i ;
        }
    }
    pali [ m ] = 1 ;
    memcpy ( v , pali , sizeof ( pali ) ) ;
}

stack < int > S ;

int main()
{
    int n , m ;
    fin >> n >> m ;
    for ( int i = 1 ; i <= n ; ++ i )
    {
        for ( int j = 1 ; j <= m ; ++ j )
        {
            fin >> mat [ i ] [ j ] ;
        }
        do_the_job( mat [ i ] , m ) ;
    }
    long long ANS = 0 ;
    /// find sol
    for ( int j = 1 ; j <= m ; ++ j )
    {
        for ( int i = 1 ; i <= n ; ++ i )
        {
            while ( !S.empty ( ) and mat [ S.top ( ) ] [ j ] >= mat [ i ] [ j ] )
            {
                int vf = S.top ( ) ;
                S.pop ( ) ;
                int L = ( ( S.empty ( ) == 1 ) ? ( 1 ): ( S.top ( ) + 1 ) ) ;
                int R = i - 1 ;
                ANS = max ( ANS , ( long long ) ( R - L + 1 ) * ( mat [ vf ] [ j ] << 1 | 1 ) ) ;
            }
            S.push ( i ) ;
        }

        ///clear
        while ( !S.empty ( ) )
            S.pop ( ) ;
    }
    fout << ANS << '\n' ;
    return 0;
}