Pagini recente » Cod sursa (job #2250637) | Cod sursa (job #1607705) | Cod sursa (job #2949640) | Cod sursa (job #75596) | Cod sursa (job #2206676)
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 210;
int n, m;
char a[NMAX][NMAX];
int b[NMAX];
int ans = -1;
int st[NMAX], top;
int stg[NMAX], drp[NMAX];
void Read()
{
ifstream fin("bmatrix.in");
fin >> n >> m;
for (int i = 1;i <= n;++i)
fin >> (a[i] + 1);
fin.close();
}
void CreateStg(int start, int finish)
{
top = 0;
st[0] = start - 1;
b[start - 1] = -1;
for (int j = start;j <= finish;++j)
{
while (top > 0 && b[j] <= b[st[top]])
--top;
stg[j] = j - st[top] - 1;
st[++top] = j;
}
}
void CreateDrp(int start, int finish)
{
top = 0;
st[0] = finish + 1;
b[finish + 1] = -1;
for (int j = finish;j >= start;--j)
{
while (top > 0 && b[j] <= b[st[top]])
--top;
drp[j] = st[top] - j - 1;
st[++top] = j;
}
}
int FirstCase(int start, int finish)
{
for (int j = 1;j <= m;++j)
b[j] = 0;
int ret = 0;
for (int i = start;i <= finish;++i)
{
for (int j = 1;j <= m;++j)
a[i][j] == '0' ? ++b[j] : b[j] = 0;
CreateStg(1, m);
CreateDrp(1, m);
for (int j = 1;j <= m;++j)
ret = max(ret, (stg[j] + drp[j] + 1) * b[j]);
}
return ret;
}
int SecondCase(int start, int finish)
{
for (int j = 1;j <= m;++j)
b[j] = 0;
int ret = 0;
for (int i = 1;i <= n;++i)
{
for (int j = start;j <= finish;++j)
a[i][j] == '0' ? ++b[j] : b[j] = 0;
CreateDrp(start, finish);
CreateStg(start, finish);
for (int j = start;j <= finish;++j)
ret = max(ret, (stg[j] + drp[j] + 1) * b[j]);
}
return ret;
}
void Solve()
{
int aux1, aux2;
for (int i = 1;i < n;++i)
{
aux1 = FirstCase(1, i);
aux2 = FirstCase(i + 1, n);
ans = max(ans, aux1 + aux2);
}
for (int j = 1;j < m;++j)
{
aux1 = SecondCase(1, j);
aux2 = SecondCase(j + 1, m);
ans = max(ans, aux1 + aux2);
}
}
void Write()
{
ofstream fout("bmatrix.out");
fout << ans << "\n";
fout.close();
}
int main()
{
Read();
Solve();
Write();
return 0;
}