Pagini recente » Cod sursa (job #44224) | Cod sursa (job #2557319) | Cod sursa (job #2363777) | Cod sursa (job #1968293) | Cod sursa (job #1253708)
#include <fstream>
#define nmax 211
using namespace std;
char lin[nmax];
int n, m, mat[nmax][nmax], st[nmax][nmax], dr[nmax][nmax], stiva[nmax];
int Drept1(int x, int n)
{
int sol = 0, a;
for (int i = x; i <= n; i++)
for (int j = 1; j <= m; j++)
{
a = dr[i][j] - st[i][j] - 1;
a *= min (mat[i][j], i - x + 1);
if (sol < a) sol = a;
}
return sol;
}
int Drept2(int y, int m)
{
int sol = 0, a;
for (int i = 1; i <= m; i++)
for (int j = y; j <= m; j++)
{
a = (min (dr[i][j], m + 1) - max (y - 1, st[i][j]) - 1) * mat[i][j];
if (sol < a) sol = a;
}
return sol;
}
int main()
{
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
fin >> n >> m;
for (int i = 1; i <= n; i++)
{
fin >> lin;
for (int j = 0; j < m; j++)
{
mat[i][j + 1] = !(lin[j] - '0');
if (mat[i][j + 1]) mat[i][j + 1] += mat[i - 1][j + 1];
}
}
for (int i = 1, cnt; i <= n; i++)
{
stiva[0] = 0;
cnt = 0;
for (int j = 1; j <= m; j++)
{
while (cnt && mat[i][stiva[cnt]] >= mat[i][j]) cnt--;
st[i][j] = stiva[cnt];
stiva[++cnt] = j;
}
cnt = 0;
stiva[0] = m + 1;
for (int j = m; j >= 1; j--)
{
while (cnt && mat[i][stiva[cnt]] >= mat[i][j]) cnt--;
dr[i][j] = stiva[cnt];
stiva[++cnt] = j;
}
}
int sol = 0;
for (int i = 2; i <= n; i++)
{
int a = Drept1(1, i - 1) + Drept1(i, n);
if (a > sol) sol = a;
}
for (int j = 2; j <= m; j++)
{
int a = Drept2(1, j - 1) + Drept2(j, m);
if (a > sol) sol = a;
}
fout << sol;
fin.close ();
fout.close ();
return 0;
}