Pagini recente » Cod sursa (job #1187450) | Cod sursa (job #1796376) | Cod sursa (job #1711264) | Clasamentul arhivei ACM | Cod sursa (job #1253049)
/*
* Code by Spiromanul
*/
#include <fstream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
const char IN [ ] = "bmatrix.in" ;
const char OUT [ ] = "bmatrix.out" ;
const int MAX = 214 ;
using namespace std;
ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;
int left_stanga [ MAX ] , right_dreapta [ MAX ] , height [ MAX ] , st [ MAX ] , MAT [ MAX ] [ MAX ] , sus [ MAX ] , jos [ MAX ] , aux [ MAX ] [ MAX ] , aux2 [ MAX ] [ MAX ] ;
char buff [ MAX ] ;
inline void solve ( int mat [ ] [ MAX ] , int *arr , int lin , int col )
{
memset ( height , 0 , sizeof ( height ) ) ;
for ( int i = 1 ; i <= lin ; ++ i )
{
for ( int j = 1 ; j <= col ; ++ j )
if ( ! mat [ i ] [ j ] )
height [ j ] ++ ;
else height [ j ] = 0 ;
int vf = 0 ;
st [ vf ] = 0 ;
for ( int j = 1 ; j <= col ; ++ j )
{
while ( vf >= 1 and height [ st [ vf ] ] >= height [ j ] )
-- vf ;
left_stanga [ j ] = st [ vf ] ;
st [ ++ vf ] = j ;
}
vf = 0 ;
st [ vf ] = col + 1 ;
for ( int j = col ; j >= 1 ; -- j )
{
while ( vf >= 1 and height [ st [ vf ] ] >= height [ j ] )
-- vf ;
right_dreapta [ j ] = st [ vf ] ;
st [ ++ vf ] = j ;
}
arr [ i ] = arr [ i - 1 ] ;
// do the job
for ( int j = 1 ; j <= col ; ++ j )
arr [ i ] = max ( arr [ i ] , ( right_dreapta [ j ] - left_stanga [ j ] - 1 ) * height [ j ] ) ;
}
}
int bussiness ( int mat [ ] [ MAX ] , int lin , int col )
{
memset ( sus , 0 , sizeof ( sus ) ) ;
memset ( jos , 0 , sizeof ( jos ) ) ;
solve ( mat , sus , lin , col ) ;
for ( int i = 1 ; i <= lin ; ++ i )
for ( int j = 1 ; j <= col ; ++ j )
aux [ lin - i + 1 ] [ j ] = mat [ i ] [ j ] ;
solve ( aux , jos , lin , col ) ;
int ce_trebuie = 1 , ham_ham = lin ;
for ( ; ce_trebuie < ham_ham ; ++ ce_trebuie , -- ham_ham )
swap ( jos [ ce_trebuie ] , jos [ ham_ham ] ) ;
ce_trebuie = 0 ;
for ( int i = 1 ; i <= lin ; ++ i )
ce_trebuie = max ( ce_trebuie , sus [ i ] + jos [ i + 1 ] ) ;
return ce_trebuie ;
}
int main( )
{
int n , m ;
fin >> n >> m ;
for ( int i = 1 ; i <= n ; ++ i )
{
fin >> buff ;
for ( int j = 0 ; j < m ; ++ j )
MAT [ i ] [ j + 1 ] = buff [ j ] - '0' ;
}
int sol1 = bussiness( MAT , n , m ) ;
for ( int i = 1 ; i <= n ; ++ i )
for ( int j = 1 ; j <= m ; ++ j )
aux2 [ j ] [ i ] = MAT [ i ] [ j ] ;
int sol2 = bussiness( aux2 , m , n ) ;
fout << max ( sol1 , sol2 ) << '\n' ;
return 0;
}