Pagini recente » Cod sursa (job #331109) | Cod sursa (job #3133341) | Monitorul de evaluare | Cod sursa (job #1376282) | Cod sursa (job #3318019)
#include <fstream>
#define INF 212
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int v[205][205], sus[205], jos[205], dr[205], st[205], n, m, h[205];
int calcArie( int dim )
{
int stiva[205], k = 0, j, left[205], right[205];
for ( j = 1; j <= dim + 1; ++j )
{
while ( k > 0 && h[stiva[k]] > h[j] )
{
right[stiva[k]] = j;
--k;
}
stiva[++k] = j;
}
k = 0;
for ( j = dim; j >= 0; --j )
{
while ( k > 0 && h[stiva[k]] > h[j] )
{
left[stiva[k]] = j;
--k;
}
stiva[++k] = j;
}
int maxim = -1;
for ( j = 1; j <= dim; ++j )
{
// fout << left[j] << " " << right[j] << endl;
int arie = h[j] * (right[j] - left[j] - 1);
maxim = max(maxim, arie);
}
return maxim;
}
int main()
{
int i, j;
fin >> n >> m;
for ( i = 1; i <= n; ++i )
for ( j = 1; j <= m; ++j )
{
char c;
fin >> c;
v[i][j] = c - '0';
}
h[0] = h[m + 1] = -INF;
for ( i = 1; i <= n; ++i )
{
for ( j = 1; j <= m; ++j )
{
if ( v[i][j] == 0 )
++h[j];
else
h[j] = 0;
}
sus[i] = max( sus[i - 1], calcArie(m));
}
for ( j = 1; j <= m; ++j )
h[j] = 0;
for ( i = n; i >= 1; --i )
{
for ( j = 1; j <= m; ++j )
{
if ( v[i][j] == 0 )
++h[j];
else
h[j] = 0;
}
jos[i] = max(jos[i + 1], calcArie(m));
}
int sol = -1;
for ( i = 1; i < n; ++i )
sol = max(sol, sus[i] + jos[i + 1]);
fout << sol << '\n';
return 0;
h[0] = h[n + 1] = -INF;
for ( j = 1; j <= m; ++j )
{
for ( i = 1; i <= n; ++i )
{
if ( v[i][j] == 0 )
++h[i];
else
h[i] = 0;
}
st[i] = max(st[i - 1], calcArie(n));
}
for ( i = 1; i <= n; ++i )
h[i] = 0;
for (j = m; j >= 1; --j )
{
for ( i = 1; i <= n; ++i )
{
if ( v[i][j] == 0 )
++h[i];
else
h[i] = 0;
}
dr[i] = max(dr[i + 1], calcArie(n));
}
for ( j = 1; j < m; ++j )
sol = max(sol, st[j] + dr[j + 1]);
fout << sol << '\n';
return 0;
}