Pagini recente » Cod sursa (job #611954) | Cod sursa (job #1058235) | Cod sursa (job #753755) | Cod sursa (job #2754450) | Cod sursa (job #1344414)
#include<fstream>
#include<string>
using namespace std;
ifstream fin( "bmatrix.in" );
ofstream fout( "bmatrix.out" );
const int nmax = 200;
const int inf = 1 << 30;
int a1, a2, n, m;
int st[ nmax + 1 ], dr[ nmax + 1 ];
int z[ nmax + 1 ][ nmax + 2 ];
bool v[ nmax + 1 ][ nmax + 1 ], aux[ nmax + 1 ][ nmax + 1 ];
string s;
int dr_max( int x, int y ) {
int zx, zy, shp, ans = 0;
for( int i = 1; i <= n; ++ i ) {
zx = z[ i ][ x - 1 ];
z[ i ][ x - 1 ] = -inf;
for( int j = x; j <= y; ++ j ) {
int k = j - 1;
while ( z[ i ][ k ] >= z[ i ][ j ] ) {
k = st[ k ];
}
st[ j ] = k;
}
zy = z[ i ][ y + 1 ];
z[ i ][ y + 1 ] = -inf;
for( int j = y; j >= x; -- j ) {
int k = j + 1;
while ( z[ i ][ k ] >= z[ i ][ j ] ) {
k = dr[ k ];
}
dr[ j ] = k;
shp = z[ i ][ j ] * (dr[ j ] - st[ j ] - 1);
if ( shp >= ans ) {
ans = shp;
}
}
z[ i ][ x - 1 ] = zx; z[ i ][ y + 1 ] = zy;
}
return ans;
}
int solve() {
int ans, shp;
ans = 0;
for( int sep = 2; sep <= m + 1; ++ sep ) {
shp = dr_max( 1, sep - 1 ) + dr_max( sep, m );
if ( ans < shp ) {
ans = shp;
}
}
return ans;
}
int main() {
int sol1, sol2, k;
fin >> n >> m;
for( int i = 1; i <= n; ++ i ) {
fin >> s;
s = "#" + s;
for( int j = 1; j <= m; ++ j ) {
aux[ i ][ j ] = v[ i ][ j ] = s[ j ] - '0';
if ( v[ i ][ j ] == 1 ) {
z[ i ][ j ] = 0;
} else {
z[ i ][ j ] = z[ i - 1 ][ j ] + 1;
}
}
}
sol1 = solve();
for( int i = 1; i <= m; ++ i ) {
for( int j = 1; j <= n; ++ j ) {
v[ i ][ j ] = aux[ j ][ i ];
if ( v[ i ][ j ] ) {
z[ i ][ j ] = 0;
} else {
z[ i ][ j ] = z[ i - 1 ][ j ] + 1;
}
}
}
k = n; n = m; m = k;
sol2 = solve();
if ( sol2 > sol1 ) {
sol1 = sol2;
}
fout << sol1 << "\n";
fin.close();
fout.close();
return 0;
}