Pagini recente » Cod sursa (job #2837425) | Cod sursa (job #879877) | Cod sursa (job #1698472) | Cod sursa (job #129187) | Cod sursa (job #1210315)
#include<fstream>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M;
char A[202][202], B[202][202];
int up[202][202];
int D[202], lft[202], rgh[202];
int maxp1[202], maxp2[202], mx1[202], mx2[202];
int result;
void compute_max(int* best, int* inc)
{
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;
else
up[i][j] = 0;
memset(best, 0, sizeof(maxp1));
for (int i = 1; i <= N; ++i)
{
D[0] = 0;
for (int j = 1; j <= M; ++j)
{
while (D[0] && up[i][D[D[0]]] >= up[i][j])
--D[0];
if (D[0] == 0) lft[j] = j;
else lft[j] = j - D[D[0]];
D[++D[0]] = j;
}
D[0] = 0;
for (int j = M; j >= 1; --j)
{
while (D[0] && up[i][D[D[0]]] >= up[i][j])
--D[0];
if (D[0] == 0) rgh[j] = M - j + 1;
else rgh[j] = D[D[0]] - j;
D[++D[0]] = j;
}
for (int j = 1; j <= M; ++j)
if (up[i][j] * (lft[j] + rgh[j] - 1) > best[i])
best[i] = up[i][j] * (lft[j] + rgh[j] - 1);
}
inc[1] = best[1];
for (int i = 2; i <= N; ++i)
inc[i] = max(inc[i - 1], best[i]);
}
void do_best()
{
compute_max(maxp1, mx1);
for (int i = 1; i <= N / 2; ++i)
for (int j = 1; j <= M; ++j)
swap(A[i][j], A[N - i + 1][j]);
compute_max(maxp2, mx2);
for (int i = 1; i <= N / 2; ++i)
for (int j = 1; j <= M; ++j)
swap(A[i][j], A[N - i + 1][j]);
for (int i = 1; i <= N; ++i)
if (mx1[i] > 0 && mx2[N - i] > 0)
result = max(result, mx1[i] + mx2[N - i]);
}
int main()
{
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
fin >> N >> M;
for (int i = 1; i <= N; ++i)
fin >> (A[i] + 1);
memcpy(B, A, sizeof(B));
do_best();
for (int i = 1; i <= M; ++i)
for (int j = 1; j <= N; ++j)
A[i][j] = B[j][i];
swap(N, M);
do_best();
fout << result << '\n';
return 0;
}