Pagini recente » Cod sursa (job #2288852) | Cod sursa (job #2273437) | Cod sursa (job #1199628) | oni_10_2 | Cod sursa (job #1316401)
#include<fstream>
using namespace std;
ifstream fin( "dreptpal.in" );
ofstream fout( "dreptpal.out" );
const int nmax = 1000;
const int inf = 1 << 30;
int m, st[ nmax + 1 ], dr[ nmax + 1 ];
int a[ nmax + 1 ][ nmax + 1 ];
int p[ nmax + 2 ][ nmax + 1 ];
void extend( int i, int j ) {
while ( j - p[ i ][ j ] >= 0 && j + p[ i ][ j ] <= m && a[ i ][ j - p[i][j] ] == a[ i ][ j + p[i][j] ] ) {
++ p[ i ][ j ];
}
}
int main() {
int n, c;
fin >> n >> m;
for( int i = 1; i <= n; ++ i ) {
for( int j = 1; j <= m; ++ j ) {
fin >> a[ i ][ j ];
}
}
for( int i = 1; i <= n; ++ i ) {
c = 1;
for( int j = 1; j <= m; ++ j ) {
if ( j > c + p[ i ][ c ] ) {
c = j;
extend( i, j );
} else {
int x = 2 * c - j;
if ( x - p[ i ][ x ] > c - p[ i ][ c ] ) {
p[ i ][ j ] = p[ i ][ x ];
} else {
p[ i ][ j ] = x - ( c - p[ i ][ c ] );
extend( i, j );
}
if ( j + p[ i ][ j ] > c + p[ i ][ c ] ) {
c = j;
}
}
}
}
int ans = 0;
for( int j = 1; j <= m; ++ j ) {
p[ 0 ][ j ] = -inf;
for( int i = 1; i <= n; ++ i ) {
int k = i - 1;
while ( p[ k ][ j ] >= p[ i ][ j ] ) {
k = st[ k ];
}
st[ i ] = k;
}
p[ n + 1 ][ j ] = -inf;
for( int i = n; i > 0; -- i ) {
int k = i + 1;
while ( p[ k ][ j ] >= p[ i ][ j ] ) {
k = dr[ k ];
}
dr[ i ] = k;
if ( ans < (dr[ i ] - st[ i ] - 1) * (2 * p[ i ][ j ] - 1) ) {
ans = (dr[ i ] - st[ i ] - 1) * (2 * p[ i ][ j ] - 1);
}
}
}
fout << ans << "\n";
fin.close();
fout.close();
return 0;
}