Mai intai trebuie sa te autentifici.
Cod sursa(job #202480)
Utilizator | Data | 8 august 2008 23:34:06 | |
---|---|---|---|
Problema | BMatrix | Scor | 16 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.9 kb |
#include <cstdio>
#include <cstring>
using namespace std;
#define FIN "bmatrix.in"
#define FOUT "bmatrix.out"
#define MAX_N 210
int A[MAX_N][MAX_N];
int mn[MAX_N][MAX_N];
short up[MAX_N][MAX_N];
short dwn[MAX_N][MAX_N];
short lft[MAX_N][MAX_N];
short rgt[MAX_N][MAX_N];
int N, M;
int BEST; // solutia
inline int MIN (int a, int b)
{
if (a < b) return a; else return b;
}
void preproc ()
{
int i, j;
for (j = 1; j <= M; ++j)
for (i = 1; i <= N; ++i)
if (A[i][j]) up[i][j] = up[i - 1][j] + 1;
for (j = 1; j <= M; ++j)
for (i = N; i; --i)
if (A[i][j]) dwn[i][j] = dwn[i + 1][j] + 1;
for (i = 1; i <= N; ++i)
for (j = 1; j <= M; ++j)
if (A[i][j]) lft[i][j] = lft[i][j - 1] + 1;
for (i = 1; i <= N; ++i)
for (j = M; j; --j)
if (A[i][j]) rgt[i][j] = rgt[i][j + 1] + 1;
}
void solve ()
{
int i, j, lin, col;
// baleiez liniile
for (lin = 1; lin <= N; ++lin)
{
int B1, B2;
B1 = B2 = 0;
for (i = 1; i <= M; ++i)
mn[i][i] = up[lin][i];
for (i = 1; i < M; ++i)
for (j = i + 1; j <= M; ++j)
mn[i][j] = MIN(mn[i][j - 1], mn[j][j]);
for (i = 1; i < M; ++i)
for (j = i + 1; j <= M; ++j)
if (mn[i][j] * (j - i + 1) > B1)
B1 = mn[i][j] * (j - i + 1);
for (i = 1; i <= M; ++i)
mn[i][i] = dwn[lin + 1][i];
for (i = 1; i < M; ++i)
for (j = i + 1; j <= M; ++j)
mn[i][j] = MIN(mn[i][j - 1], mn[j][j]);
for (i = 1; i < M; ++i)
for (j = i + 1; j <= M; ++j)
if (mn[i][j] * (j - i + 1) > B2)
B2 = mn[i][j] * (j - i + 1);
if (B1 + B2 > BEST) BEST = B1 + B2;
}
//baleiez coloanele
for (col = 1; col <= M; ++col)
{
int B1, B2;
B1 = B2 = 0;
for (i = 1; i <= N; ++i)
mn[i][i] = lft[i][col];
for (i = 1; i < N; ++i)
for (j = i + 1; j <= N; ++j)
mn[i][j] = MIN(mn[i][j - 1], mn[j][j]);
for (i = 1; i < N; ++i)
for (j = i + 1; j <= N; ++j)
if (mn[i][j] * (j - i + 1) > B1)
B1 = mn[i][j] * (j - i + 1);
for (i = 1; i <= N; ++i)
mn[i][i] = rgt[i][col + 1];
for (i = 1; i < N; ++i)
for (j = i + 1; j <= N; ++j)
mn[i][j] = MIN(mn[i][j - 1], mn[j][j]);
for (i = 1; i < N; ++i)
for (j = i + 1; j <= N; ++j)
if (mn[i][j] * (j - i + 1) > B2)
B2 = mn[i][j] * (j - i + 1);
if (B1 + B2 > BEST) BEST = B1 + B2;
}
}
int main ()
{
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
scanf ("%d %d\n", &N, &M);
int i, j;
for (i = 1; i <= N; ++i)
{
char S[250] = "";
gets (S);
for (j = 1; j <= M; ++j)
A[i][j] = S[j - 1] - '0', A[i][j] = 1 - A[i][j];
}
preproc ();
solve ();
printf ("%d\n", int (BEST));
return 0;
}