Cod sursa(job #3327429)

Utilizator RaresHRares Hanganu RaresH Data 3 decembrie 2025 20:59:27
Problema BMatrix Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <stdio.h>
#include <ctype.h>
#include <algorithm>

FILE* fin;
FILE* fout;

const int MAX_M = 200;
const int MAX_N = 200;

struct Seq {
    int len, val;
};

int m, n;
char mat[MAX_M][MAX_N], new_mat[MAX_M][MAX_N];
int max_zeros[MAX_M];
int a[MAX_N];
Seq stiva[MAX_N];

int skyline() {
    int sp = 0;
    int ret = 0;
    for(int i = 0; i < n; i++) {
        int sum = 0;
        while(sp > 0 && a[i] <= stiva[sp - 1].val) {
            sum += stiva[sp - 1].len;
            if(stiva[sp - 1].val * sum > ret) {
                ret = stiva[sp - 1].val * sum;
            }
            sp--;
        }
        stiva[sp++] = {sum + 1, a[i]};
    }
    int sum = 0;
    for(; sp > 0; sp--) {
        sum += stiva[sp - 1].len;
        if(stiva[sp - 1].val * sum > ret) {
            ret = stiva[sp - 1].val * sum;
        }
    }
    return ret;
}

int solve() {
    for(int c = 0; c < n; c++) {
        a[c] = 0;
    }
    for(int r = 0; r < m; r++) {
        for(int c = 0; c < n; c++) {
            if(mat[r][c] == 1) {
                a[c] = 0;
            } else {
                a[c]++;
            }
        }
        max_zeros[r] = skyline();
    }
    for(int c = 0; c < n; c++) {
        a[c] = 0;
    }
    int ret = max_zeros[m - 1];
    for(int r = m - 1; r > 0; r--) {
        for(int c = 0; c < n; c++) {
            if(mat[r][c] == 1) {
                a[c] = 0;
            } else {
                a[c]++;
            }
        }
        ret = std::max(ret, skyline() + max_zeros[r - 1]);
    }
    return ret;
}

char next_char() {
    char ch;
    while(isspace(ch = fgetc(fin)));
    return ch;
}

int main() {
  fin = fopen("bmatrix.in", "r");
  fout = fopen("bmatrix.out", "w");

  fscanf(fin, "%d%d", &m, &n);

  for(int r = 0; r < m; r++) {
      for(int c = 0; c < n; c++) {
          mat[r][c] = (next_char() - '0');
      }
  }

  int ans1 = solve();
  for(int r = 0; r < m; r++) {
      for(int c = 0; c < n; c++) {
          new_mat[c][r] = mat[r][c];
      }
  }
  std::swap(m, n);
  for(int r = 0; r < m; r++) {
      for(int c = 0; c < n; c++) {
          mat[r][c] = new_mat[r][c];
      }
  }
  int ans2 = solve();

  fprintf(fout, "%d\n", std::max(ans1, ans2));

  fclose(fin);
  fclose(fout);

  return 0;
}