Pagini recente » Cod sursa (job #640575) | Cod sursa (job #1133497) | Cod sursa (job #2705898) | Cod sursa (job #2581374) | Cod sursa (job #2912980)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int sUp[205][205], sDown[205][205], n, m, arieMax, dp1[205], dp2[205];
char a[205][205], b[205][205];
int lft[205], rght[205], st[205];
void Read()
{
fin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
fin >> a[i][j];
b[j][i] = a[i][j];
}
}
int Check(int s[])
{
int maxim = 0, top = 0;
st[++top] = 0;
s[0] = -1;
for(int i = 1; i <= m; i++)
{
while(s[i] <= s[st[top]])
top--;
lft[i] = i - st[top] - 1;
st[++top] = i;
}
top = 0;
st[++top] = m + 1;
s[m + 1] = -1;
for(int i = m; i >= 1; i--)
{
while(s[i] <= s[st[top]])
top--;
rght[i] = st[top] - i - 1;
st[++top] = i;
}
for(int i = 1; i <= m; i++)
maxim = max(maxim, s[i] * (lft[i] + rght[i] + 1)) ;
return maxim;
}
void Solve(char a[205][205])
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(a[i][j] == '0')
sUp[i][j] = sUp[i-1][j] + 1;
else sUp[i][j] = 0;
for(int i = n; i >= 1; i--)
for(int j = 1; j <= m; j++)
if(a[i][j] == '0')
sDown[i][j] = sDown[i+1][j] + 1;
else sDown[i][j] = 0;
for(int i = 1; i <= n; i++)
dp1[i] = max(dp1[i-1], Check(sUp[i]));
for(int i = n; i >= 1; i--)
dp2[i] = max(dp2[i+1], Check(sDown[i]));
for(int i = 1; i < n; i++)
arieMax = max(arieMax, dp1[i] + dp2[i + 1]);
}
int main()
{
Read();
Solve(a);
swap(n, m);
Solve(b);
fout << arieMax << "\n";
fout.close();
return 0;
}