Cod sursa(job #2096647)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 29 decembrie 2017 15:47:58
Problema BMatrix Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");

void Complete(int n, int m, vector < vector < char > > &mat,
    vector < vector < int > > &v, vector < vector < int > > &prop) {

  stack < int > stk;
  for (int i = 1; i <= n; i ++) {
    stk.push(0);
    mat[i][0] = '$';
    for (int j = 1; j <= m; j ++) {
      while ((mat[i][stk.top()] == mat[i][j]) and
          (prop[i][stk.top()] >= prop[i][j])) {
        stk.pop();
      }
      v[i][j] = stk.top() + 1;
      stk.push(j);
    }
  }
}

int Solve(int n, int m, vector < vector < char > > &mat) {

  vector < vector < int > > up(n + 1, vector < int > (m + 1, 1)),
    down(n + 1, vector < int > (m + 1, 1));
  
  for (int i = 2; i <= n; i ++) {
    for (int j = 1; j <= m; j ++) {
      if (mat[i][j] == mat[i - 1][j]) {
        up[i][j] = up[i - 1][j] + 1;
      }
    }
  }

  for (int i = n - 1; i >= 0; i --) {
    for (int j = 1; j <= m; j ++) {
      if (mat[i][j] == mat[i + 1][j]) {
        down[i][j] = down[i + 1][j] + 1;
      }
    }
  }

  vector < vector < int > > st_up(n + 1, vector < int > (m + 1)),
    st_down(n + 1, vector < int > (m + 1));

  Complete(n, m, mat, st_up, up); 
  Complete(n, m, mat, st_down, down); 
  
  vector < int > best_up(n + 1), best_down(n + 1);

  int previous = 0;
  for (int i = 1; i <= n; i ++) {
    
    int best = 0;
    for (int j = 1; j <= m; j ++) {
      if (mat[i][j] != '0') {
        continue;
      }

      best = max(best, (j - st_up[i][j] + 1) * up[i][j]);
    }
    previous = max(best, previous);
    best_up[i] = previous;
  }

  previous = 0;
  for (int i = n; i >= 1; i --) {
    
    int best = 0;
    for (int j = 1; j <= m; j ++) {
      if (mat[i][j] != '0') {
        continue;
      }

      best = max(best, (j - st_down[i][j] + 1) * down[i][j]);
    }
    previous = max(best, previous);
    best_down[i] = previous;
  }

  int ans = 0;
  for (int i = 1; i < n; i ++) {
    ans = max(ans, best_up[i] + best_down[i + 1]);
  }

  return ans;
}

int main() {

  int n, m;
  cin >> n >> m;

  vector < vector < char > > mat1(n + 1, vector < char > (m + 1)),
         mat2 (m + 1, vector < char > (n + 1));

  for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= m; j ++) {
      cin >> mat1[i][j];
    }
  }
  
  for (int j = 1; j <= m; j ++) {
    for (int i = n; i >= 1; i --) {
      mat2[j][n - i + 1] = mat1[i][j];
    }
  }
  
  int ans1 = Solve(n, m, mat1);
  int ans2 = Solve(m, n, mat2);
  cout << max(ans1, ans2) << '\n';
}