Pagini recente » Cod sursa (job #1802376) | Cod sursa (job #1428352) | Cod sursa (job #308263) | Cod sursa (job #3151943) | Cod sursa (job #869617)
Cod sursa(job #869617)
#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;
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 )
H1_left[i][j] = ( H1_left[i][j-1] + a[i][j] * sixe[j-1] ) % MOD1;
for ( i = 1; i <= n; ++i )
for ( j = m; j >= 1; --j )
H1_right[i][j] = ( H1_right[i][j+1] + a[i][j] * sixe[m-j] ) % MOD1;
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 )
R26 = ( R26 * sixe[zerosL-zerosR] ) % MOD1;
else R16 = ( R16 * sixe[zerosR-zerosL] ) % MOD1;
if ( R16 == R26 ) return true;
return false;
}