Pagini recente » Cod sursa (job #1702509) | Cod sursa (job #1757729) | Cod sursa (job #1102089) | Cod sursa (job #2611061) | Cod sursa (job #2504505)
#include <fstream>
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n, m, ans, nr[210][210], h[210], dr[210], st[210], sus[210], jos[210];
bool a[210][210], b[210][210];
char s[210];
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)
{ for(int i=1; i<=m; i++) h[i] = nr[poz][i];
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;
}
void rotate90()
{ for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++) b[i][j] = a[n-j+1][i];
swap(n, m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) a[i][j] = b[i][j];
}
int solve()
{ memset(sus, 0, sizeof(sus));
memset(jos, 0, sizeof(jos));
int sol = 0;
height();
for(int l=1; l<=n; l++) sus[l] = max(sus[l-1], skyline(l));
rotate90();
rotate90();
height();
for(int l=1; l<=n; l++) jos[l] = max(jos[l-1], skyline(l));
for(int i=1; i<n; i++) sol = max(sol, sus[n-i] + jos[i]);
return sol;
}
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;
}