Pagini recente » Istoria paginii runda/ioi_2020/clasament | Cod sursa (job #2383363) | Cod sursa (job #2212850) | Cod sursa (job #1214739) | Cod sursa (job #333629)
Cod sursa(job #333629)
#include<stdio.h>
#define nmax 256
#define inf 0x3f3f3f
int n,m,vs[nmax][nmax],vj[nmax][nmax],ss[nmax][nmax],sj[nmax][nmax],Sol;
char a[nmax][nmax];
int max(int x,int y)
{
if (x>y)
return x;
return y;
}
int main()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
scanf("%s",a[i]);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
{
if (a[i][j]=='0')
{
vs[i][j]=vs[i][j-1]+1;
int min=vs[i][j];
if (ss[i][j]<min)
ss[i][j]=min;
for(int k=i-1;k>=0 && vs[k][j];--k)
{
if (min>vs[k][j])
min=vs[k][j];
if (ss[i][j]<min*(i-k+1))
ss[i][j]=min*(i-k+1);
}
}
ss[i][j]=max(max(ss[i][j],ss[i-1][j]),ss[i][j-1]);
}
for(int i=n-1;i>=0;--i)
for(int j=m-1;j>=0;--j)
{
if (a[i][j]=='0')
{
vj[i][j]=vj[i][j+1]+1;
int min=vj[i][j];
if (sj[i][j]<min)
sj[i][j]=min;
for(int k=i+1;k<n && vj[k][j];++k)
{
if (min>vj[k][j])
min=vj[k][j];
if (sj[i][j]<min*(k-i+1))
sj[i][j]=min*(k-i+1);
}
}
sj[i][j]=max(sj[i][j],max(sj[i+1][j],sj[i][j+1]));
}
/*
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
printf("%d ",ss[i][j]);
printf("\n");
}
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
printf("%d ",sj[i][j]);
printf("\n");
}
*/
for(int i=0;i<n;++i)
if (Sol<ss[i][m-1]+sj[i+1][0])
Sol=ss[i][m-1]+sj[i+1][0];
for(int i=0;i<m;++i)
if (Sol<ss[n-1][i]+sj[0][i+1])
Sol=ss[n-1][i]+sj[0][i+1];
printf("%d\n",Sol);
return 0;
}