Pagini recente » Cod sursa (job #2613074) | Cod sursa (job #621042) | Cod sursa (job #165888) | Cod sursa (job #1602436) | Cod sursa (job #2764460)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("bmatrix.in");
ofstream g ("bmatrix.out");
int n, m;
int a[205][205];
int b[205][205];
int dreptunghi(int up, int down, int mt[205][205])
{
int maxim=0;
int sum[205][205];
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=m; ++j)
sum[i][j]=0;
}
for(int i=up; i<=down; ++i)
{
for(int j=1; j<=m; ++j)
if(mt[i][j]==0)
sum[i][j]=sum[i-1][j]+1;
}
for(int jos=up; jos<=down; ++jos)
{
stack <pair<int, int> > stanga;
stack <pair<int, int> > dreapta;
int st[1005]= {0};
int dr[1005]= {0};
int v[1005]= {0};
for(int i=1; i<=m; ++i)
v[i]=sum[jos][i];
stanga.push({v[1], 1});
for(int i=2; i<=m; ++i)
{
if(v[i]>=stanga.top().first)
{
stanga.push({v[i], i});
}
else
{
while(!stanga.empty() && stanga.top().first>v[i])
{
st[stanga.top().second]=i;
stanga.pop();
}
stanga.push({v[i], i});
}
}
while(!stanga.empty())
{
st[stanga.top().second]=m+1;
stanga.pop();
}
dreapta.push({v[m], m});
for(int i=m-1; i>0; --i)
{
if(v[i]>=dreapta.top().first)
{
dreapta.push({v[i], i});
}
else
{
while(!dreapta.empty() && dreapta.top().first>v[i])
{
dr[dreapta.top().second]=i;
dreapta.pop();
}
dreapta.push({v[i], i});
}
}
while(!dreapta.empty())
{
dr[dreapta.top().second]=0;
dreapta.pop();
}
for(int i=1; i<=m; ++i)
{
if(maxim<v[i]*(st[i]-dr[i]-1))
{
maxim=v[i]*(st[i]-dr[i]-1);
}
maxim=max(maxim, v[i]*(st[i]-dr[i]-1));
}
}
return maxim;
}
int solve(int mt[205][205])
{
int maxim=0;
for(int linie=1; linie<n; ++linie)
{
int x=dreptunghi(1, linie, mt);
int y=dreptunghi(linie+1, n, mt);
maxim=max(maxim, x+y);
}
return maxim;
}
int main()
{
f>>n>>m;
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=m; ++j)
{
char x;
f>>x;
a[i][j]=x-'0';
b[j][i]=x-'0';
}
}
int x=solve(a);
swap(n, m);
int y=solve(b);
g<<max(x, y);
return 0;
}