Pagini recente » Cod sursa (job #2182653) | Cod sursa (job #913944) | Cod sursa (job #1780683) | Cod sursa (job #609824) | Cod sursa (job #2921073)
#include <bits/stdc++.h>
#define NMAX 208
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
char a[NMAX][NMAX];
long long r[NMAX][NMAX], c[NMAX][NMAX], sus[NMAX], jos[NMAX], dr[NMAX], st[NMAX];
long long ans, n, m;
void arie();
int main()
{
fin >> n >> m;
for (long long i = 1; i <= n; i++)
for (long long j = 1; j <= m; j++)
fin >> a[i][j];
arie();
///calcul raspuns
for (long long i = 1; i < n; i++)
ans = max(ans, sus[i] + jos[i+1]);
for (long long i = 1; i < m; i++)
ans = max(ans, st[i] + dr[i+1]);
fout << ans;
return 0;
}
void arie()
{
long long total_area = 0, area, minc, left, right;
for (long long i = 1; i <= n; i++)
{
if (a[i][1] == '0')
r[i][1] = 1;
else
r[i][1] = 0;
for (long long j = 2; j <= m; j++)
{
if (a[i][j] == '1')
r[i][j] = 0;
else
r[i][j] = r[i][j-1] + 1;
}
for (long long j = 1; j <= m; j++)
{
if (i == 1)
c[1][j] = (a[1][j] == '1' ? 0:1);
else
{
if (a[i][j] == '0')
c[i][j] = c[i-1][j] + 1;
else
c[i][j] = 0;
}
}
}
for (long long i = 1; i <= n; i++)
for (long long j = 1; j <= m; j++)
{
area = 0;
if (a[i][j] == '0')
{
minc = c[i][j];
area = minc;
left = j;
for (long long k = j-1; k >= 1; k--)
{
if (c[i][k] == 0)
break;
minc = min(minc, c[i][k]);
if (minc * (j - k + 1) > area)
{
area = minc * (j - k + 1);
left = k;
}
}
}
sus[i] = max(max(sus[i], sus[i - 1]),area);
st[j] = max(max(st[j], st[j - 1]),area);
}
for (long long i = n; i >= 1; i--)
{
if (a[i][m] == '0')
r[i][m] = 1;
else
r[i][m] = 0;
for (long long j = m-1; j >= 1; j--)
{
if (a[i][j] == '1')
r[i][j] = 0;
else
r[i][j] = r[i][j+1] + 1;
}
for (long long j = m; j >= 1; j--)
{
if (i == n)
c[n][j] = (a[n][j] == '1' ? 0:1);
else
{
if (a[i][j] == '0')
c[i][j] = c[i+1][j] + 1;
else
c[i][j] = 0;
}
}
}
for (long long i = n; i >= 1; i--)
for (long long j = m; j >= 1; j--)
{
area = 0;
if (a[i][j] == '0')
{
minc = c[i][j];
area = minc;
for (long long k = j+1; k <= m; k++)
{
if (c[i][k] == 0)
break;
minc = min(minc, c[i][k]);
if (minc * (k - j + 1) > area)
{
area = minc * (k - j + 1);
}
}
}
jos[i] = max(max(jos[i], jos[i + 1]),area);
dr[j] = max(max(dr[j], dr[j + 1]),area);
}
}