Cod sursa(job #869643)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 1 februarie 2013 21:55:09
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <fstream>
#define MOD1 666013
using namespace std;
#define LE 1066
ifstream f ( "dreptpal.in" );
ofstream g ( "dreptpal.out" );
int sixe[LE];
int n, H1_left[LE][LE], H1_right[LE][LE];
int a[LE][LE];
int i, j, m;
bool equalx ( int X, int Y, int step );
int palmax ( int X, int Y );
pair<int, int> stiva[LE];
int result;
int best_left[LE];
int best_right[LE];
int V[LE], top, sum;
#define ll long long

int main()
{
    f >> n >> m;
    sixe[0] = 1;

    for ( i = 1; i <= m ; ++i )
        sixe[i] = ( sixe[i-1] * 666 ) % MOD1;

    for ( i = 1; i <= n; ++i )
        for ( j = 1; j <= m; ++j ) f >> a[i][j];

    for ( i = 1; i <= n; ++i )
        for ( j = 1; j <= m; ++j )
        {
            ll PP= (ll)H1_left[i][j-1] + (ll)a[i][j] * (ll)sixe[j-1] ;
            PP%=MOD1;

            H1_left[i][j] = PP;
        }

    for ( i = 1; i <= n; ++i )
        for ( j = m; j >= 1; --j )
        {
            ll PP=(ll)H1_right[i][j+1]  + (ll)a[i][j] * (ll)sixe[m-j] ;
            PP%=MOD1;
            H1_right[i][j] =PP;
        }

    for ( i = 1; i <= n; ++i )
        for ( j = 1; j <= m; ++j )
            a[i][j] = palmax ( i, j );


    for ( i = 1; i <= m; ++i )
    {
        for ( j = 1; j <= n; ++j )
            V[j] = a[j][i];

        for ( top = 0, j = 1; j <= n; ++j )
        {
            sum = 0;

            while ( top > 0 && stiva[top].first >= V[j] )
                sum += stiva[top--].second;

            stiva[++top] = make_pair ( V[j], sum + 1 );
            best_left[j] = sum + 1;
        }

        for ( top = 0, j = n; j >= 1; --j )
        {
            sum = 0;

            while ( top > 0 && stiva[top].first >= V[j] )
                sum += stiva[top--].second;

            stiva[++top] = make_pair ( V[j], sum + 1 );
            best_right[j] = sum + 1;
        }

        for ( j = 1; j <= n; ++j )
            result = max ( result, ( best_left[j] + best_right[j] - 1 ) * a[j][i] );
    }


    g << result << '\n';




    f.close();
    g.close();
    return 0;
}

int palmax ( int X, int Y )
{
    int step, pos;

    for ( step = 1; step <= m; step *= 2 );

    for ( pos = 0; step; step /= 2 )
        if ( equalx ( X, Y, pos + step ) == true )
            pos += step;

    return pos * 2 + 1;
}
bool equalx ( int X, int Y, int step )
{
    if ( Y - step < 1 || Y + step > m ) return false;


    int R16 = ( MOD1 + H1_left[X][Y-1] - H1_left[X][Y-step-1] ) % MOD1;
    int  R26 = ( MOD1 + H1_right[X][Y+1] - H1_right[X][Y+step+1] ) % MOD1;

    int zerosR = m - ( Y + step );
    int zerosL = Y - step - 1;

    if ( zerosL > zerosR )
        {
            ll PP=(ll)R26 * (ll)sixe[zerosL-zerosR];
            PP%=MOD1;
            R26 = PP;
        }
    else
    {
        ll PP=(ll)R16 * (ll)sixe[zerosR-zerosL];
        PP%=MOD1;
        R16 =PP;
    }
    if ( R16 == R26 ) return true;

    return false;
}