Cod sursa(job #1507630)

Utilizator spatarelDan-Constantin Spatarel spatarel Data 21 octombrie 2015 19:31:17
Problema BMatrix Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 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 = 1; c <= M; ++ 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]);
    if (dr1 != 0 && dr2 != 0)
      ans = max(ans, dr1 + dr2);
  }
}

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

  ans = 0;
  computeMaxDr();
  solve();
  /*
  for(register int l = 1; l <= N; ++l) {
    for(register int c = 1; c <= M; ++c) {
      printf("%d ", mat[l][c]);
    }
    printf("\n");
  }
  printf("\n");
  for(register int l = 1; l <= N; ++l) {
    for(register int c = 1; c <= N; ++c) {
      printf("%d ", maxDr[l][c]);
    }
    printf("\n");
  }
  printf("\n");//*/
  reverseMatrix();
  computeMaxDr();
  solve();

  /*
  for(register int l = 1; l <= N; ++l) {
    for(register int c = 1; c <= M; ++c) {
      printf("%d ", mat[l][c]);
    }
    printf("\n");
  }
  printf("\n");
  for(register int l = 1; l <= N; ++l) {
    for(register int c = 1; c <= N; ++c) {
      printf("%d ", maxDr[l][c]);
    }
    printf("\n");
  }
  printf("\n");//*/

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