Cod sursa(job #2799452)

Utilizator alextmAlexandru Toma alextm Data 13 noiembrie 2021 11:05:45
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 205;

char v[MAXN][MAXN];

// Numarul de elemente de '0' in fiecare directie
int Left[MAXN][MAXN], Right[MAXN][MAXN];
int Up[MAXN][MAXN], Down[MAXN][MAXN];

// Aria maxima a unui dreptunghi in cele 4 directii
int drUp[MAXN], drDown[MAXN];
int drRight[MAXN], drLeft[MAXN];

int Histogram(int n, int m, int H[]) {
	int val[MAXN];
	val[0] = val[n + 1] = -1; // Santinela
	for(int i = 1; i <= n; i++)
		val[i] = min(m, H[i]);

	vector<int> L(MAXN);
	stack<int> st; st.push(0);

	for(int i = 1; i <= n; i++) {
		while(val[st.top()] >= val[i])
			st.pop();
		
		L[i] = i - st.top();
		st.push(i);
	}

	while(!st.empty()) st.pop();
	st.push(n + 1);

	vector<int> R(MAXN);
	for(int i = n; i >= 1; i--) {
		while(val[st.top()] >= val[i])
			st.pop();
		
		R[i] = st.top() - i;
		st.push(i);
	}

	int ans = 0;
	for(int i = 1; i <= n; i++)
		ans = max(ans, val[i] * (R[i] + L[i] - 1));
	return ans;
}

int main() {
	int n, m, k;
	
	fin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			fin >> v[i][j];

			Up[i][j] = (v[i][j] == '0' ? Up[i - 1][j] + 1 : 0);
			Left[j][i] = (v[i][j] == '0' ? Left[j - 1][i] + 1 : 0);
		}

	for(int i = n; i >= 1; i--)
		for(int j = m; j >= 1; j--) {
			Down[i][j] = (v[i][j] == '0' ? Down[i + 1][j] + 1 : 0);
			Right[j][i] = (v[i][j] == '0' ? Right[j + 1][i] + 1 : 0);
		}


	for(int i = 1; i <= n; i++)
		drUp[i] = max(drUp[i - 1], Histogram(m, i, Up[i]));

	for(int j = 1; j <= m; j++)
		drLeft[j] = max(drLeft[j - 1], Histogram(n, j, Left[j]));

	for(int i = n; i >= 1; i--)
		drDown[i] = max(drDown[i + 1], Histogram(m, n - i + 1, Down[i]));

	for(int j = m; j >= 1; j--)
		drRight[j] = max(drRight[j + 1], Histogram(n, m - j + 1, Right[j]));

	int answer = 0;
	for(int i = 1; i <= n; i++)
		answer = max(answer, drUp[i] + drDown[i + 1]);

	for(int j = 1; j <= m; j++)
		answer = max(answer, drLeft[j] + drRight[j + 1]);

	fout << answer << "\n";

	return 0;
}