Pagini recente » Cod sursa (job #2894121) | Cod sursa (job #2568685) | Cod sursa (job #274104) | Cod sursa (job #1358128) | Cod sursa (job #2444329)
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n,m;
int a[205][205],b[205][205],h[205],stiva[205],cnt,st[205],dr[205],dp[5][205];
void roteste()
{for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
b[j][n+1-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];
}
}
}
void rezolva(int dir)
{
for(int i=1;i<=m;i++)
{
h[i]=0;
}
for(int i=1;i<=n;i++)
{dp[dir][i]=dp[dir][i-1];
for(int j=1;j<=m;j++)
{
if(a[i][j]==0)
{
h[j]=h[j]+1;
}
else h[j]=0;
}
stiva[0]=0;
cnt=0;
for(int j=1;j<=m;j++)
{
while(cnt>0&&(h[stiva[cnt]]>=h[j]))
{
cnt--;
}
st[j]=stiva[cnt];
stiva[++cnt]=j;
}
cnt=0;
stiva[0]=m+1;
for(int j=m;j>=1;j--)
{
while(cnt>0&&(h[stiva[cnt]]>=h[j]))
{
cnt--;
}
dr[j]=stiva[cnt];
stiva[++cnt]=j;
}
for(int j=1;j<=m;j++)
{
if(dp[dir][i]<h[j]*(dr[j]-st[j]-1))
{
dp[dir][i]=h[j]*(dr[j]-st[j]-1);
}
}
}
}
int main()
{
f>>n>>m;
char c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f>>c;
a[i][j]=int(c-48);
}
}
for(int i=1;i<=4;i++)
{rezolva(i);
roteste();
}
int sol=0;
for(int i=1;i<=n;i++)
{
sol=max(sol,dp[1][i]+dp[3][n-i]);
}
for(int i=1;i<=m;i++)
{
sol=max(sol,dp[2][i]+dp[4][m-i]);
}
g<<sol;
}