Pagini recente » Cod sursa (job #2310540) | Cod sursa (job #1907917) | Cod sursa (job #63341) | Cod sursa (job #2968003) | Cod sursa (job #1992989)
#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 (int m, int n)
{
for (int i=1; i<=m; i++)
{
for (int j=1; j<=n; j++)
{
aux[n-j+1][i] = A[i][j];
}
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
{
A[i][j] = aux[i][j];
}
}
return;
}
int sol (int m, int n)
{
int solution=0;
for (int k=1; k<=m; k++)
{
int up=0;
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(m,n);
int s2 = sol(n,m);
cout<<max(s1, s2)<<'\n';
return 0;
}