Pagini recente » Cod sursa (job #1494580) | Cod sursa (job #1923085) | Cod sursa (job #2914992) | Cod sursa (job #885772) | Cod sursa (job #2332596)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int DN=205;
int n,m;
char a[DN][DN],b[DN][DN];
int dp[4][DN][DN],ma,lg[DN][DN],nr,val,cnt[DN][DN],f,lst[DN];
void solve()
{
for(int i=0;i<=n+1;i++)
for(int j=0;j<=m+1;j++)
lg[i][j]=dp[0][i][j]=dp[1][i][j]=cnt[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i][j]=='1')
continue;
lg[i][j]=1+lg[i-1][j];
}
for(int type=0;type<2;type++)
{
for(int i=1;i<=n;i++)
//for(int h=1;h<=i;h++)
{
nr=0;
for(int j=1;j<=m;j++)
{
if(lg[i][j]==0)
continue;
f=j-1;
while(lg[i][f]>=lg[i][j])
f=lst[f];
lst[j]=f;
cnt[i][j]=j-f;
}
lg[i][m+1]=0;
for(int j=m;j>0;j--)
{
if(lg[i][j]==0)
continue;
f=j+1;
while(lg[i][f]>=lg[i][j])
f=lst[f];
lst[j]=f;
cnt[i][j]+=f-j-1;
}
for(int j=1;j<=m;j++)
{
if(lg[i][j]==0)
continue;
int h=i-lg[i][j]+1;
dp[type][i][j]=max(dp[type][i][j],cnt[i][j]*lg[i][j]);
}
}
for(int i=n;i>0;i--)
for(int j=1;j<=m;j++)
{
lg[i][j]=0;
if(a[i][j]=='1')
continue;
lg[i][j]=1+lg[i+1][j];
}
}
f=0;
for(int i=n;i>0;i--)
{
for(int j=1;j<=m;j++)
f=max(f,dp[1][i+1][j]);
for(int j=1;j<=m;j++)
ma=max(ma,dp[0][i][j]+f);
}
}
int main()
{
fin>>n>>m;
for(int i=0;i<=n;i++)
fin.getline(a[i]+1,DN);
solve();
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];
solve();
fout<<ma;
}