Pagini recente » Cod sursa (job #3345774) | Cod sursa (job #3348963) | Cod sursa (job #2584450) | Cod sursa (job #3340462) | Cod sursa (job #3318162)
#include <bits/stdc++.h>
using namespace std;
const int NMAX=2005;
int n,m,a[NMAX][NMAX];
long long h[NMAX];
int st[NMAX],dr[NMAX],s[NMAX];
long long skyline(long long h[],int m){
long long r=0;
int st1[NMAX],dr1[NMAX],s1[NMAX],sp;
sp=0;
for(int j=1;j<=m;j++){
while(sp>0&&h[s1[sp]]>=h[j])
sp--;
if(sp==0)
st1[j]=0;
else
st1[j]=s1[sp];
s1[++sp]=j;
}
sp=0;
for(int j=m;j>=1;j--){
while(sp>0&&h[s1[sp]]>=h[j])
sp--;
if(sp==0)
dr1[j]=m+1;
else
dr1[j]=s1[sp];
s1[++sp]=j;
}
for(int j=1;j<=m;j++){
long long l=dr1[j]-st1[j]-1;
long long aria=h[j]*l;
if(aria>r)r=aria;
}
return r;
}
int main(){
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
fin>>n>>m;
for(int i=1;i<=n;i++){
string x;
fin>>x;
for(int j=1;j<=m;j++)
a[i][j]=x[j-1]-'0';
}
long long sus[NMAX],jos[NMAX],rasp=0,amax;
for(int j=1;j<=m;j++)
h[j]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==0)
h[j]=h[j]+1;
else
h[j]=0;
}
amax=skyline(h,m);
if(i==1)
sus[i]=amax;
else
sus[i]=max(sus[i-1],amax);
}
for(int j=1;j<=m;j++)h[j]=0;
for(int i=n;i>=1;i--){
for(int j=1;j<=m;j++){
if(a[i][j]==0)
h[j]=h[j]+1;
else
h[j]=0;
}
amax=skyline(h,m);
if(i==n)
jos[i]=amax;
else
jos[i]=max(jos[i+1],aMax);
}
for(int i=1;i<n;i++)
rasp=max(rasp,sus[i]+jos[i+1]);
int b[NMAX][NMAX];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[j][i]=a[i][j];
swap(n,m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=b[i][j];
for(int j=1;j<=m;j++)
h[j]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==0)
h[j]=h[j]+1;
else
h[j]=0;
}
amax=skyline(h,m);
if(i==1)
sus[i]=amax;
else
sus[i]=max(sus[i-1],amax);
}
for(int j=1;j<=m;j++)
h[j]=0;
for(int i=n;i>=1;i--){
for(int j=1;j<=m;j++){
if(a[i][j]==0)
h[j]=h[j]+1;
else
h[j]=0;
}
amax=skyline(h,m);
if(i==n)
jos[i]=amax;
else
jos[i]=max(jos[i+1],amax);
}
for(int i=1;i<n;i++)
rasp=max(rasp,sus[i]+jos[i+1]);
fout<<rasp<<"\n";
return 0;
}