Cod sursa(job #603663)

Utilizator cont_de_testeCont Teste cont_de_teste Data 18 iulie 2011 12:11:00
Problema BMatrix Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
# include <cstdio>
# include <cstring>

const char *FIN = "bmatrix.in", *FOU = "bmatrix.out";
const int MAX = 205;

int N, M, sol;
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) {
    int area[MAX], J[MAX][MAX], S[MAX][MAX];

    /*for (int i = 0; i <= N + 1; ++i) {
        area[i] = 0;
        for (int j = 0; j <= N + 1; ++j)
            J[i][j] = S[i][j] = 0;
    }*/
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            S[i][j] = (bmat[i][j] == '0' ? (i == 1 ? 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);
        }
    }
    area[0] = 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);
}