Cod sursa(job #2030244)

Utilizator GoogalAbabei Daniel Googal Data 1 octombrie 2017 12:53:23
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <memory.h>
#include <fstream>
#include <cstring>
#include <stack>

using namespace std;

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

const int NMAX = 200;

struct Data {
  int val;
  int sum;
};

int n, m, res;
int fv[1 + NMAX];
int dp[4][1 + NMAX];
bool v[1 + NMAX][1 + NMAX];
bool v2[1 + NMAX][1 + NMAX];
char s[2 * NMAX];

stack < Data > st;

void rotatemat() {
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      v2[j][n - i + 1] = v[i][j];
    }
  }

  swap(n, m);
  memcpy(v, v2, sizeof(v));
}

void solve(int z) {
  fill(fv, fv + NMAX + 1, 0);
  for(int i = 1; i <= n; i++) {
    dp[z][i] = dp[z][i - 1];
    for(int j = 1; j <= m + 1; j++) {
      if(v[i][j] == 0 && j <= m)
        fv[j]++;
      else
        fv[j] = 0;
      int sum = 0;
      while(!st.empty() && fv[j] <= st.top().val) {
        Data from = st.top();
        st.pop();
        sum += from.sum;
        dp[z][i] = max(dp[z][i], sum * from.val);
      }
      st.push({fv[j], sum + 1});
    }
  }
}

int main()
{
  in >> n >> m;
  in.get();
  for(int i = 1; i <= n; i++) {
    in.getline(s, 2 * NMAX);
    for(int j = 0; j < m; j++) {
      v[i][j + 1] = s[j] - '0';
    }
  }

  for(int i = 0; i < 4; i++) {
    solve(i);
    rotatemat();
  }

  for(int i = 1; i <= n; i++) {
    res = max(res, dp[0][i] + dp[2][n - i]);
  }

  for(int i = 1; i <= m; i++) {
    res = max(res, dp[1][i] + dp[3][m - i]);
  }

  out << res << '\n';
  in.close();
  out.close();
  return 0;
}