Pagini recente » Cod sursa (job #1384473) | Cod sursa (job #2695894) | Cod sursa (job #2470863) | Cod sursa (job #2382406) | Cod sursa (job #2504493)
#include <fstream>
#include <iostream>
#include <cstring>
#include <stack>
#define NMAX 200
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n, m, ans, nr[NMAX+10][NMAX+10], h[NMAX+10], dr[NMAX+10], st[NMAX+10];
bool a[NMAX+10][NMAX+10], b[NMAX+10][NMAX+10];
char s[NMAX+10];
stack <int> stiva;
void height()
{ memset(nr, 0, sizeof(nr));
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{ if(a[i][j]) nr[i][j] = 0;
else nr[i][j] = nr[i-1][j] + 1;
}
}
int skyline(int poz, int line)
{ for(int i=1; i<=m; i++) h[i] = min(nr[poz][i], poz-line);
while(!stiva.empty()) stiva.pop();
stiva.push(1);
st[1] = 0;
for(int i=2; i<=m; i++)
{ while(!stiva.empty() && h[i] <= h[stiva.top()]) stiva.pop();
if(stiva.empty()) st[i] = 0;
else st[i] = stiva.top();
stiva.push(i);
}
while(!stiva.empty()) stiva.pop();
stiva.push(m);
dr[m] = m+1;
for(int i=m-1; i>=1; i--)
{ while(!stiva.empty() && h[i] <= h[stiva.top()]) stiva.pop();
if(stiva.empty()) dr[i] = m+1;
else dr[i] = stiva.top();
stiva.push(i);
}
int sol = 0;
for(int i=1; i<=m; i++) sol = max(sol, h[i] * (dr[i]-st[i]-1));
return sol;
}
int solve()
{ int sol = 0;
height();
for(int l=1; l<n; l++)
{ int sol1 = 0, sol2 = 0;
for(int i=1; i<=l; i++) sol1 = max(sol1, skyline(i, 0));
for(int i=l+1; i<=n; i++) sol2 = max(sol2, skyline(i, l));
sol = max(sol, sol1 + sol2);
}
return sol;
}
void rotate90()
{ for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++) b[j][i] = a[i][j];
swap(n, m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) a[i][j] = b[i][j];
}
int main()
{
f >> n >> m;
for(int i=1; i<=n; i++)
{ f >> s;
for(int j=0; j<m; j++) a[i][j+1] = s[j] - '0';
}
ans = solve();
rotate90();
ans = max(ans, solve());
g << ans << '\n';
return 0;
}