Pagini recente » Cod sursa (job #168319) | Cod sursa (job #3343468) | Cod sursa (job #868669) | Cod sursa (job #3349209) | Cod sursa (job #3316265)
#include <iostream>
#include <fstream>
#define NMAX 1005
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
char c[NMAX][NMAX];
long long vsus[NMAX][NMAX],vjos[NMAX][NMAX],vst[NMAX][NMAX],vdr[NMAX][NMAX];
long long l[NMAX],r[NMAX],sus[NMAX],jos[NMAX],st[NMAX],dr[NMAX],s[NMAX];
int n,m;
void bordare()
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(c[i][j]=='0')
vsus[i][j]=vsus[i-1][j]+1;
else vsus[i][j]=0;
}
}
for(int i=n; i>=1; i--)
{
for(int j=1; j<=m; j++)
{
if(c[i][j]=='0')
vjos[i][j]=vjos[i+1][j]+1;
else vjos[i][j]=0;
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(c[i][j]=='0')
vst[i][j]=vst[i][j-1]+1;
else vst[i][j]=0;
}
}
for(int i=1; i<=n; i++)
{
for(int j=m; j>=1; j--)
{
if(c[i][j]=='0')
vdr[i][j]=vdr[i][j+1]+1;
else vdr[i][j]=0;
}
}
}
int main()
{
long long ans=0;
fin>>n>>m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
fin>>c[i][j];
}
}
bordare();
for(int i=1; i<=n; i++)
{
int k=0;
s[0]=0;
for(int j=1; j<=m; j++)
{
while(k>0 && vsus[i][j]<=vsus[i][s[k]])
{
k--;
}
l[j]=s[k];
k++;
s[k]=j;
}
k=0;
s[0]=m+1;
for(int j=m; j>=1; j--)
{
while(k>0 && vsus[i][j]<=vsus[i][s[k]])
{
k--;
}
r[j]=s[k];
k++;
s[k]=j;
}
for(int j=1; j<=m; j++)
{
sus[i]=max(sus[i], vsus[i][j]*(r[j]-l[j]-1));
}
}
for(int i=n; i>=1; i--)
{
int k=0;
s[0]=0;
for(int j=1; j<=m; j++)
{
while(k>0 && vjos[i][j]<=vjos[i][s[k]])
{
k--;
}
l[j]=s[k];
k++;
s[k]=j;
}
k=0;
s[0]=m+1;
for(int j=m; j>=1; j--)
{
while(k>0&&vjos[i][j]<=vjos[i][s[k]])
{
k--;
}
r[j]=s[k];
k++;
s[k]=j;
}
for(int j=1; j<=m; j++)
{
jos[i]=max(jos[i],vjos[i][j]*(r[j]-l[j]-1));
}
}
for(int j=1; j<=m; j++)
{
int k=0;
s[0]=0;
for(int i=1; i<=n; i++)
{
while(k>0 && vst[i][j]<=vst[s[k]][j])
{
k--;
}
l[i]=s[k];
k++;
s[k]=i;
}
k=0;
s[0]=n+1;
for(int i=n; i>=1; i--)
{
while(k>0 && vst[i][j]<=vst[s[k]][j])
{
k--;
}
r[i]=s[k];
k++;
s[k]=i;
}
for(int i=1; i<=n; i++)
{
st[j]=max(st[j], vst[i][j]*(r[i]-l[i]-1));
}
}
for(int j=m; j>=1; j--)
{
int k=0;
s[0]=0;
for(int i=1; i<=n; i++)
{
while(k>0 && vdr[i][j] <= vdr[s[k]][j])
{
k--;
}
l[i]=s[k];
k++;
s[k]=i;
}
k=0;
s[0]=n+1;
for(int i=n; i>=1; i--)
{
while(k>0 && vdr[i][j]<=vdr[s[k]][j])
{
k--;
}
r[i]=s[k];
k++;
s[k]=i;
}
for(int i=1; i<=n; i++)
{
dr[j]=max(dr[j], vdr[i][j]*(r[i]-l[i]-1));
}
}
for(int i=1; i<n; i++)
{
ans=max(ans,sus[i]+jos[i+1]);
}
for(int j=1; j<m; j++)
{
ans=max(ans,st[j]+dr[j+1]);
}
fout<<ans;
return 0;
}