Pagini recente » Cod sursa (job #723964) | Cod sursa (job #1563868) | Cod sursa (job #2698744) | Cod sursa (job #321731) | Cod sursa (job #1387316)
#include <fstream>
#include <stack>
#include <cstring>
using namespace std;
#define NMAX 207
stack < pair < int , int > > q;
int h[NMAX],sol[NMAX];
int t[NMAX][NMAX];
string str;
int i,j,N,M,ans;
int solve(int x1,int y1,int x2,int y2)
{
memset(h,0,sizeof(h));
int i,j,ans=0;
for (i=x1;i<=x2;++i)
{
for (j=y1;j<=y2;++j)
while (q.size()) q.pop();
for (j=y1;j<=y2;++j)
{
h[j] = (t[i][j]) ? h[j]+1 : 0;
while (q.size() && q.top().first>=h[j])
q.pop();
if (q.empty()) sol[j] = j - y1 + 1;
else sol[j] = j - q.top().second;
q.push(make_pair(h[j],j));
}
while (q.size()) q.pop();
for (j=y2;j>=y1;--j)
{
while (q.size() && q.top().first>=h[j])
q.pop();
if (q.empty()) sol[j] += y2 - j;
else sol[j] += q.top().second - j - 1;
ans = max (ans , sol[j]*h[j]);
q.push(make_pair(h[j],j));
}
}
return ans;
}
int main()
{
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
f>>N>>M;
for (i=1;i<=N;++i)
{
f>>str;
for (j=0;j<M;++j)
t[i][j+1]=(str[j]=='0');
}
for (i=1;i<=N;++i)
ans=max(ans,solve(1,1,i,M)+solve(i+1,1,N,M));
for (i=1;i<=M;++i)
ans=max(ans,solve(1,1,N,i)+solve(1,i+1,N,M));
g<<ans<<'\n';
return 0;
}