Cod sursa(job #1693448)

Utilizator sucureiSucureiRobert sucurei Data 23 aprilie 2016 09:18:23
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#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;
}