Pagini recente » Cod sursa (job #1876593) | Cod sursa (job #145737) | Cod sursa (job #2368645) | Cod sursa (job #2147708) | Cod sursa (job #869643)
Cod sursa(job #869643)
#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;
}