Pagini recente » Cod sursa (job #572202) | Cod sursa (job #998463) | Cod sursa (job #216109) | Utilizatori inregistrati la Infoarena Monthly 2012 - Runda 6 | Cod sursa (job #357322)
Cod sursa(job #357322)
#include <cstdio>
#define MAX_N 205
int N, M;
char A[MAX_N][MAX_N];
int Ln_sus[MAX_N], Ln_jos[MAX_N], Col_st[MAX_N], Col_dr[MAX_N];
inline int max(const int &A, const int &B) {return ((A) > (B))? (A) : (B);}
inline int min(const int &A, const int &B) {return ((A) < (B))? (A) : (B);}
void citire()
{
scanf("%d %d\n",&N, &M);
for(int i = 1; i <= N; ++i)
fgets(A[i]+1, MAX_N, stdin);
}
void solve()
{
int B[MAX_N][MAX_N];
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
B[i][j] = (A[i][j] == '0')? B[i][j-1]+1 : 0;
/*for(int i = 1; i <= N; ++i)
{
for(int j = 1; j <= M; ++j)
printf("%d ",B[i][j]);
printf("\n");
}*/
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
{
Ln_sus[i] = max(Ln_sus[i], B[i][j]);
int act = B[i][j];
for(int k = i-1; k; --k)
{
act = min(act, B[k][j]);
Ln_sus[i] = max(Ln_sus[i], act*(i - k + 1));
}
Ln_jos[i] = max(Ln_jos[i], B[i][j]);
act = B[i][j];
for(int k = i+1; k <= N; ++k)
{
act = min(act, B[k][j]);
Ln_jos[i] = max(Ln_jos[i], act*(k - i + 1));
}
}
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
B[i][j] = (A[i][j] == '0')? B[i-1][j]+1 : 0;
/*for(int i = 1; i <= N; ++i)
{
for(int j = 1; j <= M; ++j)
printf("%d ",B[i][j]);
printf("\n");
}*/
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
{
Col_st[j] = max(Col_st[j], B[i][j]);
int act = B[i][j];
for(int k = j-1; k; --k)
{
act = min(act, B[i][k]);
Col_st[j] = max(Col_st[j], act*(j-k+1));
}
Col_dr[j] = max(Col_dr[j], B[i][j]);
act = B[i][j];
for(int k = j+1; k <= M; ++k)
{
act = min(act, B[i][k]);
Col_dr[j] = max(Col_dr[j], act*(k-j+1));
}
}
int Sol = 0;
/*for(int i = 1; i <= N; ++i) printf("%d %d\n",Ln_sus[i], Ln_jos[i]);
printf("\n\n");
for(int i = 1; i <= M; ++i) printf("%d %d\n",Col_st[i], Col_dr[i]);
*/
for(int i = 1; i <= N; ++i) Ln_sus[i] = max(Ln_sus[i], Ln_sus[i-1]);
for(int i = 1; i <= N; ++i) Ln_sus[i] = max(Ln_sus[i], Ln_sus[i-1]);
for(int i = N; i; --i) Ln_jos[i] = max(Ln_jos[i], Ln_jos[i+1]);
for(int j = 1; j <= M; ++j) Col_st[j] = max(Col_st[j], Col_st[j-1]);
for(int j = M; j; --j) Col_dr[j] = max(Col_dr[j], Col_dr[j+1]);
for(int i = 1; i <= N; ++i) Sol = max(Sol, Ln_sus[i] + Ln_jos[i+1]);
for(int j = 1; j <= M; ++j) Sol = max(Sol, Col_st[j] + Col_dr[j+1]);
printf("%d\n",Sol);
}
int main()
{
freopen("bmatrix.in","rt",stdin);
freopen("bmatrix.out","wt",stdout);
citire();
solve();
}