Pagini recente » Cod sursa (job #2161949) | Cod sursa (job #1646241) | Cod sursa (job #519537) | Cod sursa (job #2463892) | Cod sursa (job #1993685)
#include <fstream>
#include <stack>
using namespace std;
ifstream cin ("bmatrix.in");
ofstream cout ("bmatrix.out");
char sir[205];
int A[205][205];
int aux[205][205];
int h[205][205];
int l[205][205];
int st[205];
int dr[205];
stack <int> lft;
stack <int> rgt;
void intors(){
for(int i=1;i<=200;i++){
for(int j=i+1;j<=200;j++){
swap(A[i][j],A[j][i]);
}
}
return;
}
int sol (int m, int n)
{
int solution=0;
int up=0;
for (int k=1; k<=m; k++)
{
int down=0;
while (!lft.empty())
{
lft.pop();
}
while (!rgt.empty())
{
rgt.pop();
}
lft.push(0);
rgt.push(n+1);
for (int j=1; j<=n; j++)
{
while (h[k][j] <= h[k][lft.top()] && lft.size()>1)
{
lft.pop();
}
st[j]=lft.top();
lft.push(j);
}
for (int j=n; j>=1; j--)
{
while (h[k][j] <= h[k][rgt.top()] && rgt.size()>1)
{
rgt.pop();
}
dr[j]=rgt.top();
rgt.push(j);
}
for (int j=1; j<=n; j++)
{
up=max(up, h[k][j] * (dr[j] - st[j] -1));
}
//up done
while (!lft.empty())
{
lft.pop();
}
while (!rgt.empty())
{
rgt.pop();
}
lft.push(0);
rgt.push(n+1);
for (int j=1; j<=n; j++)
{
while (l[k+1][j] <= l[k+1][lft.top()] && lft.size()>1)
{
lft.pop();
}
st[j]=lft.top();
lft.push(j);
}
for (int j=n; j>=1; j--)
{
while (l[k+1][j] <= l[k+1][rgt.top()] && rgt.size()>1)
{
rgt.pop();
}
dr[j]=rgt.top();
rgt.push(j);
}
for (int j=1; j<=n; j++)
{
down=max(down, l[k+1][j] * (dr[j] - st[j] -1));
}
//down done
solution=max(solution, up + down);
}
return solution;
}
int main()
{
int m, n;
cin>>m>>n;
for (int i=1; i<=m; i++)
{
cin>>(sir+1);
for (int j=1; j<=n; j++)
{
A[i][j]=sir[j]-'0';
}
}
for (int i=1; i<=m; i++)
{
for (int j=1; j<=n; j++)
{
if (A[i][j] == 0)
{
h[i][j] = h[i-1][j] + 1;
}
if (A[i][j] == 1)
{
h[i][j] = 0;
}
}
}
for (int i=m; i>=1; i--)
{
for (int j=1; j<=n; j++)
{
if (A[i][j] == 0)
{
l[i][j] = l[i+1][j] + 1;
}
else
{
l[i][j] = 0;
}
}
}
int s1 = sol(m,n);
intors();
swap (n,m);
for (int i=0; i<=m+1; i++){
for (int j=0; j<=n+1; j++){
h[i][j]=0;
l[i][j]=0;
}
}
for (int i=1; i<=m; i++)
{
for (int j=1; j<=n; j++)
{
if (A[i][j] == 0)
{
h[i][j] = h[i-1][j] + 1;
}
if (A[i][j] == 1)
{
h[i][j] = 0;
}
}
}
for (int i=m; i>=1; i--)
{
for (int j=1; j<=n; j++)
{
if (A[i][j] == 0)
{
l[i][j] = l[i+1][j] + 1;
}
else
{
l[i][j] = 0;
}
}
}
int s2 = sol(m,n);
cout<<max(s1, s2)<<'\n';
return 0;
}