Pagini recente » Cod sursa (job #406403) | Cod sursa (job #1366324) | Cod sursa (job #1033470) | Cod sursa (job #41502) | Cod sursa (job #2989776)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int N, M, up[202][202], D[202], lft[202], rgh[202], maxp1[202], maxp2[202], mx1[202], mx2[202], result;
char A[202][202], B[202][202];
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(){
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;
return 0;
}