Pagini recente » Clasament concurs-mihai-patrascu-2013 | Cod sursa (job #2659297) | Cod sursa (job #2661157) | Cod sursa (job #3232626) | Cod sursa (job #1471802)
#include<stdio.h>
#include<algorithm>
#include<stack>
#define mp make_pair
#define maxn 205
using namespace std;
int n,m,sol;
char a[maxn][maxn];
int up[maxn][maxn],dw[maxn][maxn],dp_up[maxn],dp_dw[maxn];
int left[maxn][maxn],right[maxn][maxn],dp_left[maxn],dp_right[maxn];
int L[2][maxn],R[2][maxn];
stack< pair<int,int> > s[2];
void read()
{
scanf("%d %d\n",&n,&m);
for(int i=1;i<=n;i++) scanf("%s\n",a[i]+1);
}
void DP_vertical()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if(a[i][j]=='0')
up[i][j]=up[i-1][j]+1;
for(int i=n;i;i--)
for(int j=1;j<=m;j++) if(a[i][j]=='0')
dw[i][j]=dw[i+1][j]+1;
for(int i=1;i<=n;i++)
{
dp_up[i]=dp_dw[i]=0;
//from left to right
for(int j=1;j<=m;j++)
{
while(!s[0].empty() && up[i][j]<s[0].top().first)
R[0][s[0].top().second]=j,s[0].pop();
s[0].push(mp(up[i][j],j));
while(!s[1].empty() && dw[i][j]<s[1].top().first)
R[1][s[1].top().second]=j,s[1].pop();
s[1].push(mp(dw[i][j],j));
}
for(;!s[0].empty();s[0].pop()) R[0][s[0].top().second]=m+1;
for(;!s[1].empty();s[1].pop()) R[1][s[1].top().second]=m+1;
//from right to left
for(int j=m;j;j--)
{
while(!s[0].empty() && up[i][j]<s[0].top().first)
L[0][s[0].top().second]=j,s[0].pop();
s[0].push(mp(up[i][j],j));
while(!s[1].empty() && dw[i][j]<s[1].top().first)
L[1][s[1].top().second]=j,s[1].pop();
s[1].push(mp(dw[i][j],j));
}
for(;!s[0].empty();s[0].pop()) L[0][s[0].top().second]=0;
for(;!s[1].empty();s[1].pop()) L[1][s[1].top().second]=0;
//result on a line
for(int j=1;j<=m;j++)
{
dp_up[i]=max(dp_up[i],up[i][j]*(R[0][j]-L[0][j]-1));
dp_dw[i]=max(dp_dw[i],dw[i][j]*(R[1][j]-L[1][j]-1));
}
}
int UP,DW;
for(int i=1;i<n;i++)
{
UP=DW=0;
for(int j=1;j<=i;j++) UP=max(UP,dp_up[j]);
for(int j=i+1;j<=n;j++) DW=max(DW,dp_dw[j]);
sol=max(sol,UP+DW);
}
}
void DP_horizontal()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if(a[i][j]=='0')
left[i][j]=left[i][j-1]+1;
for(int i=1;i<=n;i++)
for(int j=m;j;j--) if(a[i][j]=='0')
right[i][j]=right[i][j+1]+1;
for(int i=1;i<=m;i++)
{
dp_left[i]=dp_right[i]=0;
//from top to bottom
for(int j=1;j<=n;j++)
{
while(!s[0].empty() && left[j][i]<s[0].top().first)
R[0][s[0].top().second]=j,s[0].pop();
s[0].push(mp(left[j][i],j));
while(!s[1].empty() && right[j][i]<s[1].top().first)
R[1][s[1].top().second]=j,s[1].pop();
s[1].push(mp(right[j][i],j));
}
for(;!s[0].empty();s[0].pop()) R[0][s[0].top().second]=n+1;
for(;!s[1].empty();s[1].pop()) R[1][s[1].top().second]=n+1;
//down - up
for(int j=n;j;j--)
{
while(!s[0].empty() && left[j][i]<s[0].top().first)
L[0][s[0].top().second]=j,s[0].pop();
s[0].push(mp(left[j][i],j));
while(!s[1].empty() && right[j][i]<s[1].top().first)
L[1][s[1].top().second]=j,s[1].pop();
s[1].push(mp(right[j][i],j));
}
for(;!s[0].empty();s[0].pop()) L[0][s[0].top().second]=0;
for(;!s[1].empty();s[1].pop()) L[1][s[1].top().second]=0;
//result on a column
for(int j=1;j<=n;j++)
{
dp_left[i]=max(dp_left[i],left[j][i]*(R[0][j]-L[0][j]-1));
dp_right[i]=max(dp_right[i],right[j][i]*(R[1][j]-L[1][j]-1));
}
}
int LEFT,RIGHT;
for(int i=1;i<m;i++)
{
LEFT=RIGHT=0;
for(int j=1;j<=i;j++) LEFT=max(LEFT,dp_left[j]);
for(int j=i+1;j<=m;j++) RIGHT=max(RIGHT,dp_right[j]);
sol=max(sol,LEFT+RIGHT);
}
}
int main()
{
freopen("bmatrix.in","r",stdin);
freopen("bmatrix.out","w",stdout);
read();
DP_vertical();
DP_horizontal();
printf("%d",sol);
fclose(stdin);
fclose(stdout);
return 0;
}