Cod sursa(job #2447713)

Utilizator Iulia25Hosu Iulia Iulia25 Data 14 august 2019 13:11:10
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <fstream>
#include <stack>
#include <cstring>

using namespace std;

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

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

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

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;
}