Pagini recente » Cod sursa (job #2988261) | Cod sursa (job #2115738) | Cod sursa (job #2282814) | Cod sursa (job #1555715) | Cod sursa (job #2430419)
#include <bits/stdc++.h>
#define Dim 205
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int N,M,dp[5][Dim][Dim][Dim],B[5][Dim],ans;
char A[Dim][Dim];
int main()
{
f>>N>>M; f.get();
for(int i=1;i<=N;i++,f.get())
for(int j=1;j<=M;j++) f>>A[i][j];
for(int i=N;i>=1;i--)
for(int j=M;j>=1;j--)
for(int k=1;i+k-1<=N;k++)
if(A[i+k-1][j]=='0')
{
dp[1][i][j][k]=dp[1][i][j+1][k]+k;
B[1][i]=max(B[1][i+1],dp[1][i][j][k]);
}
else break;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
{
int reper=0;
for(int k=1;k<=i;k++)
if(A[k][j]=='0')
{
dp[2][i][j][k-reper]=dp[2][i][j-1][k-reper]+k-reper;
B[2][i]=max(B[2][i-1],dp[2][i][j][k-reper]);
}
else reper=k;
}
for(int j=1;j<=M;j++)
{
int reper=0;
for(int i=1;i<=N;i++)
if(A[i][j]=='0')
{
dp[3][i][j][i-reper]=dp[3][i][j-1][i-reper]+i-reper;
B[3][j]=max(B[3][j-1],dp[3][i][j][i-reper]);
}
else reper=i;
}
for(int j=M;j>=1;j--)
{
int reper=0;
for(int i=1;i<=N;i++)
if(A[i][j]=='0')
{
dp[4][i][j][i-reper]=dp[4][i][j][i-reper]+i-reper;
B[4][j]=max(B[4][j+1],dp[4][i][j][i-reper]);
}
else reper=i;
}
for(int i=1;i<N;i++) ans=max(ans,B[2][i]+B[1][i+1]);
for(int j=1;j<M;j++) ans=max(ans,B[3][j]+B[4][j+1]);
g<<ans;
return 0;
}