Pagini recente » Cod sursa (job #1642672) | Cod sursa (job #2899945) | Cod sursa (job #1834534) | Cod sursa (job #675766) | Cod sursa (job #2837264)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int NMAX=205;
int N, M, s1[NMAX][NMAX], s2[NMAX][NMAX], d1[NMAX], d2[NMAX];
char mat[NMAX][NMAX];
stack<int> st1, st2;
int left_smaller[NMAX], right_smaller[NMAX], h[NMAX];
int largetHistogramArea(int L)
{
while(!st1.empty()) st1.pop();
while(!st2.empty()) st2.pop();
///find the first smallest from left
st1.push(0);
h[0]=-1;
for(int i=1;i<=L;i++){
while(h[i]<=h[st1.top()])
st1.pop();
left_smaller[i]=st1.top();
st1.push(i);
}
///find the first smallest from right
st2.push(L+1);
h[L+1]=-1;
for(int i=L;i>=1;i--){
while(h[i]<=h[st2.top()])
st2.pop();
right_smaller[i]=st2.top();
st2.push(i);
}
int mx=0;
for(int i=1;i<=L;i++)
mx=max(mx,(right_smaller[i]-left_smaller[i]-1)*h[i]);
return mx;
}
int solve()
{
for(int i=0;i<=N+1;i++){
for(int j=0;j<=M+1;j++){
s1[i][j]=0;
s2[i][j]=0;
d1[i]=d1[j]=0;
d2[i]=d2[j]=0;
}
}
///from the line i to the top
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
if(mat[i][j]=='0')
s1[i][j]=s1[i-1][j]+1;
else
s1[i][j]=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++)
h[j]=s1[i][j];
d1[i]=max(d1[i-1],largetHistogramArea(M));
}
///from the line i to the bottom
for(int i=N;i>=1;i--)
for(int j=1;j<=M;j++)
if(mat[i][j]=='0')
s2[i][j]=s2[i+1][j]+1;
else
s2[i][j]=0;
for(int i=N;i>=1;i--){
for(int j=1;j<=M;j++)
h[j]=s2[i][j];
d2[i]=max(d2[i+1],largetHistogramArea(M));
}
int sol=0;
for(int i=1;i<N;i++)
sol=max(sol,d1[i]+d2[i+1]);
return sol;
}
int main()
{
fin>>N>>M;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
fin>>mat[i][j];
int sol=0;
sol=max(sol,solve());
fout<<sol<<'\n';
fin.close();
fout.close();
return 0;
}