Pagini recente » Cod sursa (job #3353510) | Cod sursa (job #1009809) | Cod sursa (job #3322965) | Cod sursa (job #3314645) | Cod sursa (job #3315897)
#include <iostream>
#include <fstream>
#define NMAX 1005
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
char c[NMAX][NMAX];
long long a[NMAX], l[NMAX], r[NMAX], sus[NMAX], jos[NMAX], st[NMAX], dr[NMAX], s[NMAX];
int main()
{
int n, m;
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];
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(c[i][j]=='0')
{
a[j]++;
}
else a[j]=0;
}
int k=0;
s[0]=0;
for(int j=1; j<=m; j++)
{
while(k>0 && a[j]<=a[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 && a[j]<=a[s[k]])
k--;
r[j]=s[k];
k++;
s[k]=j;
}
for(int j=1; j<=m; j++)
{
st[j]=max(st[j-1], a[j]*(r[j]-l[j]-1));
sus[i]=max(sus[i-1], a[j]*(r[j]-l[j]-1));
}
}
for(int j=1; j<=m; j++) a[j]=0;
for(int i=n; i>=1; i--)
{
for(int j=1; j<=m; j++)
{
if(c[i][j]=='0') a[j]++;
else a[j]=0;
}
int k=0;
s[0]=0;
for(int j=1; j<=m; j++)
{
while(k>0 && a[j]<=a[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 && a[j]<=a[s[k]])
k--;
r[j]=s[k];
k++;
s[k]=j;
}
for(int j=m; j>=1; j--)
{
dr[j]=max(dr[j+1], a[j]*(r[j]-l[j]-1));
jos[i]=max(jos[i+1], a[j]*(r[j]-l[j]-1));
}
}
for(int j=1; j<m; j++)
{
ans=max(ans, st[j]+dr[j+1]);
}
for (int i=1; i<n; i++)
{
ans=max(ans, sus[i]+jos[i + 1]);
}
fout<<ans;
return 0;
}