Cod sursa(job #1507617)

Utilizator tudorcomanTudor Coman tudorcoman Data 21 octombrie 2015 19:25:09
Problema BMatrix Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using std::max;

const int maxN = 200;

int N, M, ans;
bool mat[1 + maxN + 1][1 + maxN + 1];
int maxDr[1 + maxN + 1][1 + maxN + 1];

template<typename T>
void swap(T &a, T &b) {
    if (a != b) {
        a = a xor b;
        b = a xor b;
        a = a xor b;
    }
}

void reverseMatrix() {
    memset(maxDr, 0, sizeof maxDr);
    for(register int i = 1; i <= N; ++ i)
        for(register int j = i + 1; j <= M; ++ j)
            swap(mat[i][j], mat[j][i]);
    swap(N, M);
}

void computeMaxDr() {
    for(register int l1 = 1; l1 <= N; ++ l1) {
        bool a[1 + maxN + 1];
        memset(a, true, sizeof a);
        for(register int l2 = l1; l2 <= N; ++ l2){
            for(register int c = 1; c <= M; ++ c)
                a[c] &= mat[l2][c];
            int l = 0, lmax = 0;
            for(register int c = M; c > 0; -- c) {
                if(a[c]) ++ l;
                else l = 0;
                lmax = max(l, lmax);
            }
            maxDr[l1][l2] = lmax * (l2 - l1 + 1);
        }
    }
}

void solve() {
    for(register int L = 1; L < N; ++ L) {
        int dr1 = 0, dr2 = 0;
        for(register int l1 = 1; l1 <= L; ++ l1)
            for(register int l2 = l1; l2 <= L; ++ l2)
                dr1 = max(dr1, maxDr[l1][l2]);
        for(register int l1 = L + 1; l1 <= N; ++ l1)
            for(register int l2 = l1; l2 <= N; ++ l2)
                dr2 = max(dr2, maxDr[l1][l2]);
        ans = max(ans, dr1 + dr2);
    }
}

int main(void) {
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);
    scanf("%d%d\n", &N, &M);
    for(register int l = 1; l <= N; ++ l, getc(stdin))
        for(register int c = 1; c <= M; ++ c) {
            char ch;
            ch = getc(stdin);
            mat[l][c] = ch - '0';
            mat[l][c] = !mat[l][c];
        }
    ans = 0;
    computeMaxDr();
    solve();
    reverseMatrix();
    computeMaxDr();
    solve();

    printf("%d\n", ans);
    return 0;
}