Cod sursa(job #2447737)

Utilizator Iulia25Hosu Iulia Iulia25 Data 14 august 2019 14:33:54
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <cstring>
#include <stack>

using namespace std;

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

int n, m, a[205][205], s[205], Max, st[205], dr[205];
int max_sus[205], max_jos[205];
stack <int> d;

void fjaoisdfjl()  {
  max_sus[0] = max_jos[n + 1] = 0;
  for (int l = 1; l <= n; ++l)  {
    max_sus[l] = max_sus[l - 1];
    for (int c = 1; c <= m; ++c)
      if (a[l][c] == 0)
        ++s[c];
      else s[c] = 0;
    for (int c = 1; c <= m; ++c)  {
      while (!d.empty() && s[d.top()] >= s[c])
        d.pop();
      if (!d.empty())
        st[c] = d.top() + 1;
      else st[c] = 1;
      d.push(c);
    }
    while (!d.empty())
      d.pop();
    for (int c = m; c; --c)  {
      while (!d.empty() && s[d.top()] >= s[c])
        d.pop();
      if (!d.empty())
        dr[c] = d.top() - 1;
      else dr[c] = m;
      d.push(c);
      max_sus[l] = max(max_sus[l], (dr[c] - st[c] + 1) * s[c]);
    }
    while (!d.empty())
      d.pop();
  }
  memset(s, 0, sizeof(s));
  memset(dr, 0, sizeof(dr));
  memset(st, 0, sizeof(st));
  for (int l = n; l; --l)  {
    max_jos[l] = max_jos[l + 1];
    for (int c = 1; c <= m; ++c)
      if (a[l][c] == 0)
        ++s[c];
      else s[c] = 0;
    for (int c = 1; c <= m; ++c)  {
      while (!d.empty() && s[d.top()] >= s[c])
        d.pop();
      if (!d.empty())
        st[c] = d.top() + 1;
      else st[c] = 1;
      d.push(c);
    }
    while (!d.empty())
      d.pop();
    for (int c = m; c; --c)  {
      while (!d.empty() && s[d.top()] >= s[c])
        d.pop();
      if (!d.empty())
        dr[c] = d.top() - 1;
      else dr[c] = m;
      d.push(c);
      max_jos[l] = max(max_jos[l], (dr[c] - st[c] + 1) * s[c]);
    }
    while (!d.empty())
      d.pop();
  }
  memset(s, 0, sizeof(s));
  memset(dr, 0, sizeof(dr));
  memset(st, 0, sizeof(st));
	for (int i = 1; i < n; ++i)
    Max = max(Max, max_sus[i] + max_jos[i + 1]);
  memset(max_sus, 0, sizeof(max_sus));
  memset(max_jos, 0, sizeof(max_jos));
}

int main()  {
	fin >> n >> m;
	char c;
	for (int i = 1; i <= n; ++i)  {
		for (int j = 1; j <= m; ++j)  {
			fin >> c;
			a[i][j] = c - '0';
		}
	}
	fjaoisdfjl();
	fin.close();
	ifstream fin("bmatrix.in");
	fin >> n >> m;
	char caracterfsjefdn;
	for (int i = 1; i <= n; ++i)  {
		for (int j = 1; j <= m; ++j)  {
			fin >> caracterfsjefdn;
			a[j][i] = caracterfsjefdn - '0';
		}
	}
	swap(n, m);
	fjaoisdfjl();
	fout << Max;
	return 0;
}