Cod sursa(job #603658)
# include <cstdio>
# include <cstring>
const char *FIN = "bmatrix.in", *FOU = "bmatrix.out";
const int MAX = 205;
int N, M, sol;
int area[MAX], J[MAX][MAX], S[MAX][MAX];
char bmat[MAX][MAX];
inline void swap (int &a, int &b) {
int aux = a; a = b; b = aux;
}
inline void swap (char &a, char &b) {
int aux = a; a = b; b = aux;
}
inline void getmin (int &a, int b) {
a = a < b ? a : b;
}
inline void getmax (int &a, int b) {
a = a > b ? a : b;
}
inline void solve (void) {
memset (area, 0, sizeof (area));
memset (J, 0, sizeof (J));
memset (S, 0, sizeof (S));
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
S[i][j] = (bmat[i][j] == '0' ? S[i - 1][j] + 1 : 0);
J[N - i + 1][j] = (bmat[N - i + 1][j] == '0' ? J[N - i + 2][j] + 1 : 0);
}
}
for (int i = 1; i <= N; ++i) {
area[i] = area[i - 1];
for (int j = 1; j <= M; ++j) {
int min = MAX;
for (int k = j; k <= M; ++k) {
getmin (min, S[i][k]);
getmax (area[i], min * (k - j + 1));
}
}
}
for (int i = N; i; --i) {
for (int j = 1; j <= M; ++j) {
int min = MAX;
for (int k = j; k <= M; ++k) {
getmin (min, J[i][k]);
getmax (sol, area[i - 1] + min * (k - j + 1));
}
}
}
}
int main (void) {
freopen (FIN, "r", stdin);
scanf ("%d %d\n", &N, &M);
for (int i = 1; i <= N; ++i)
fgets (bmat[i] + 1, MAX, stdin);
solve ();
for (int i = 1; i <= N || i <= M; ++i)
for (int j = i + 1; j <= N || j <= M; ++j)
swap (bmat[i][j], bmat[j][i]);
swap (N, M);
solve ();
fprintf (fopen (FOU, "w"), "%d", sol);
}