Cod sursa(job #1804407)

Utilizator TincaMateiTinca Matei TincaMatei Data 12 noiembrie 2016 15:39:30
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>

const int MAX_N = 200;
const int INFINIT = 1000000000;
int sus[MAX_N];
int matr[MAX_N][MAX_N];

int bestl1[MAX_N];
int bestc1[MAX_N];
int bestl2[MAX_N];
int bestc2[MAX_N];

int main() {
  int n, m, min, r;
  char ch;
  FILE *fin = fopen("bmatrix.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for(int l = 0; l < n; ++l)
    for(int c = 0; c < m; ++c) {
      ch = fgetc(fin);
      while(ch != '0' && ch != '1')
        ch = fgetc(fin);
      matr[l][c] = ch - '0';
    }
  fclose(fin);

  for(int l = 0; l < n; ++l)
    for(int c = 0; c < m; ++c) {
      if(matr[l][c] == 0)
        sus[c]++;
      else
        sus[c] = 0;
      min = INFINIT;
      for(int h = 1; c - h + 1 >= 0; h++) {
        if(sus[c - h + 1] < min)
          min = sus[c - h + 1];
        if(bestl1[l] < h * min)
          bestl1[l] = h * min;
        if(bestc1[c] < h * min)
          bestc1[c] = h * min;
      }
    }

  for(int c = 0; c < m; ++c)
    sus[c] = 0;
  for(int l = n - 1; l >= 0; --l) {
    for(int c = m - 1; c >= 0; --c) {
      if(matr[l][c] == 0)
        sus[c]++;
      else
        sus[c] = 0;
      min = INFINIT;
      for(int h = 1; c + h - 1 <= m; ++h) {
        if(sus[c + h - 1] < min)
          min = sus[c + h - 1];
        if(bestl2[l] < h * min)
          bestl2[l] = h * min;
        if(bestc2[c] < h * min)
          bestc2[c] = h * min;
      }
    }
  }

  r = 0;
  for(int l = 0; l < n; ++l)
    for(int l2 = l + 1; l2 < n; ++l2)
      if(bestl1[l] + bestl2[l2] > r)
        r = bestl1[l] + bestl2[l2];
  for(int c = 0; c < m; ++c)
    for(int c2 = c + 1; c2 < m; ++c2)
      if(bestc1[c] + bestc2[c2] > r)
        r = bestc1[c] + bestc2[c2];

  FILE *fout = fopen("bmatrix.out", "w");
  fprintf(fout, "%d", r);
  fclose(fout);
  return 0;
}