Pagini recente » Cod sursa (job #2699500) | Cod sursa (job #945480) | Cod sursa (job #2304811) | Cod sursa (job #2834393) | Cod sursa (job #3205170)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
int test[201][201],mat[201][201],n,m;
void transfer( int x1,int y1,int x2,int y2)
{
for( int i = x1; i <= x2; i ++ )
{
for ( int j = y1 ; j <= y2; j ++ )
{
test[i-x1+1][j-y1+1] = mat[i][j];
}
}
}
void liniar( vector<int> &st, vector<int> &dr, vector<int> &v, int n )
{
stack<int> stiva;
for ( int i = 1; i <= n ; i ++ )
{
while ( !stiva.empty() && v[stiva.top() ] > v[i])
{
dr[stiva.top()] = i ;
stiva.pop();
}
stiva.push(i);
}
while (!stiva.empty() )
{
dr[stiva.top() ] = n + 1;
stiva.pop();
}
for ( int i = n ; i >= 1 ; i -- )
{
while (!stiva.empty() && v[stiva.top()] > v[i])
{
st[stiva.top() ] = i ;
stiva.pop();
}
stiva.push(i);
}
while (!stiva.empty())
{
st[stiva.top()] = 0 ;
stiva.pop();
}
}
int solve(int n, int m )
{
int ans = 0 ;
vector<int> h(m+2,0);
for ( int i = 1; i <= n ; i ++ )
{
for ( int j = 1; j <= m ; j ++ )
{
if ( test[i][j] == 0)
h[j] ++ ;
else
h[j] = 0 ;
}
vector<int> st(m+2);
vector<int> dr (m+2);
liniar(st,dr,h,m);
for ( int j = 1; j <= m ; j ++ )
{
int cst = st[j] + 1;
int cdr = dr[j] - 1;
ans = max ( ans, ( cdr - cst + 1) * h[j]);
}
}
return ans ;
}
int main()
{
cin >> n >> m;
int fin = 0 ;
for ( int i = 1; i <= n ; i ++)
for ( int j = 1; j <= m ; j ++ )
{
char c;
cin >> c;
if ( c== '1')
mat[i][j] = 1;
}
for ( int i = 1; i <= n ; i ++ )
{
transfer(1,1,i,m);
int val1 = solve(i,m);
transfer(i +1, 1, n, m );
int val2 = solve(n - i,m);
fin = max ( fin, val2 + val1) ;
}
for( int i = 1 ; i <= m ; i ++ )
{
transfer(1,1,n,i);
int val1 = solve(n,i);
transfer(1,i+1,n,m);
int val2 = solve(n, m - i );
fin = max ( fin ,val1 + val2);
}
cout << fin << '\n';
return 0;
}