Pagini recente » Monitorul de evaluare | Statistici popovici mircea (mirceapgab) | Cod sursa (job #716014) | Cod sursa (job #3343901) | Cod sursa (job #3318166)
#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) {
int st[NMAX], dr[NMAX], s[NMAX];
long long sump[NMAX];
sump[0]=0;
for (int i=1;i<=m;i++)
sump[i]=sump[i-1]+1;
int sp=0;
for (int i=1;i<=m;i++) {
while (sp>0 && h[s[sp]]>=h[i])
sp--;
if (sp==0)
st[i]=0;
else
st[i]=s[sp];
s[++sp]=i;
}
sp=0;
for (int i=m;i>=1;i--) {
while (sp>0 && h[s[sp]]>=h[i])
sp--;
if (sp==0)
dr[i]=m+1;
else
dr[i]=s[sp];
s[++sp]=i;
}
long long rasp=0;
for (int i=1;i<=m;i++) {
long long lung=sump[dr[i]-1]-sump[st[i]];
long long aria=h[i]*lung;
if (aria>rasp)
rasp=aria;
}
return rasp;
}
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;
}