Pagini recente » Cod sursa (job #2922383) | Cod sursa (job #2263305) | Cod sursa (job #1362224) | Cod sursa (job #1499567) | Cod sursa (job #1693448)
#include <cstdio>
#include <cstring>
#define DIM 256
#define INF 2000000000
using namespace std;
FILE *fin = fopen("bmatrix.in" ,"r");
FILE *fout= fopen("bmatrix.out","w");
int D[DIM][DIM];
char S[DIM];
int best[5][DIM],A[DIM][DIM];
int E[3][DIM], d, maxim, aux;
int N, M, i, j, k, C[DIM][DIM];
int poz;
void SetUp() {
fscanf(fin, "%d%d", &N, &M);
for(i = 1; i <= N; i ++) {
fscanf(fin, "%s", &S);
for(j = 0; j < M; j ++)
A[i][j+1] = S[j] - '0';
}
return;
}
void Rotate_Matrix() {
for(i = 1; i <= N; i ++)
for(j = 1; j <= M; j ++)
C[j][N-i+1] = A[i][j];
aux = N;
N = M;
M = aux;
for(i = 1; i <= N; i ++)
for(j = 1; j <= M; j ++)
A[i][j] = C[i][j];
return;
}
void Partial() {
memset(D, 0, sizeof(D));
for(i = 1; i <= N; i ++)
for(j = 1; j <= M; j ++)
if(A[i][j] == 0)
D[i][j] = D[i-1][j] + 1;
else
D[i][j] = 0;
return;
}
void BMatrix() {
for(d = 1; d <= 4; d ++) {
Partial();
for(i = 1; i <= N; i ++) {
maxim = 0;
k = 0;
for(j = 1; j <= M + 1; j ++) {
if(D[i][j] > E[1][k]) {
k ++;
E[1][k] = D[i][j];
E[2][k] = j;
}
else {
while(D[i][j] <= E[1][k] && k > 0) {
if(maxim < E[1][k] * (j - E[2][k]))
maxim = E[1][k] * (j - E[2][k]);
poz = E[2][k];
k --;
}
if(D[i][j] != 0) {
k ++;
E[1][k] = D[i][j];
E[2][k] = poz;
}
}
}
best[d][i] = maxim;
}
Rotate_Matrix();
}
return;
}
void Remake() {
maxim = 0;
for(i = 1; i <= N; i ++) {
if(maxim < best[1][i])
maxim = best[1][i];
best[1][i] = maxim;
}
maxim = 0;
for(j = 1; j <= M; j ++) {
if(maxim < best[2][j])
maxim = best[2][j];
best[2][j] = maxim;
}
maxim = 0;
for(i = 1; i <= N; i ++) {
if(maxim < best[3][i])
maxim = best[3][i];
best[3][i] = maxim;
}
maxim = 0;
for(j = 1; j <= M; j ++) {
if(maxim < best[4][j])
maxim = best[4][j];
best[4][j] = maxim;
}
return;
}
void Finish() {
maxim = 0;
for(i = 1; i < N; i ++)
if(maxim < best[1][i] + best[3][N-i])
maxim = best[1][i] + best[3][N-i];
for(j = 1; j < M; j ++)
if(maxim < best[2][j] + best[4][M-j])
maxim = best[2][j] + best[4][M-j];
fprintf(fout, "%d", maxim);
return;
}
int main() {
SetUp();
BMatrix();
Remake();
Finish();
return 0;
}