Cod sursa(job #1823022)

Utilizator greenadexIulia Harasim greenadex Data 5 decembrie 2016 20:04:26
Problema BMatrix Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
 
using namespace std;
 
const string name = "bmatrix",
             in_file = name + ".in",
             out_file = name + ".out";
 
ifstream fin(in_file);
ofstream fout(out_file);
 
const int MAX = 201;

int n, m;
int matrix[MAX][MAX];
int heights[MAX][MAX];
vector<int> stackk;
int lefty[MAX], righty[MAX];
int dp[MAX][MAX];

void build_heights(int x1, int y1, int x2, int y2) {
	memset(heights, 0, sizeof(heights));
	
	for (int i = x1; i <= x2; i++) {
		for (int j = y1; j <= y2; j++) {
			if (matrix[i][j]) {
				heights[i][j] = 0;
			} else {
				heights[i][j] = heights[i - 1][j] + 1;
			}
		}
	}
}

int go(int x1, int y1, int x2, int y2) {
	build_heights(x1, y1, x2, y2);
	int maxx = 0;
	for (int i = x1; i <= x2; i++) {
		stackk.clear();
		for (int j = y1; j <= y2; j++) {
			int height = heights[i][j];
			
			if (!height) {
				lefty[j] = 0;
				stackk.clear();
				continue;
			}
			
			while (!stackk.empty() && heights[i][stackk.back()] > height) {
				stackk.pop_back();
			}

			if (stackk.empty() || heights[i][stackk.back()] < height) {
				stackk.push_back(j);
				lefty[j] = j;
			} else {
				lefty[j] = stackk.back();
			}
		}

		stackk.clear();
		for (int j = y2; j > 0; j--) {
			int height = heights[i][j];

			if (!height) {
				righty[j] = 0;
				stackk.clear();
				continue;
			}

			while (!stackk.empty() && heights[i][stackk.back()] > height) {
				stackk.pop_back();
			}

			if (stackk.empty() || heights[i][stackk.back()] < height) {
				stackk.push_back(j);
				righty[j] = j;
			} else {
				righty[j] = stackk.back();
			}

		}

		for (int j = y1; j <= y2; j++) {
			dp[i][j] = heights[i][j] * (righty[j] - lefty[j] + 1);
			maxx = max(dp[i][j], maxx);
		}
	}
	return maxx;
}

int main() {
	fin >> n >> m;
	
	string str;
	for (int i = 1; i <= n; i++) {
		fin >> str;
		for (int j = 1; j <= m; j++) {
			matrix[i][j] = str[j - 1] - '0';
		}
	}

	int result = 0;
	for (int line = 1; line < n; line++) {
		int topLeftSecond = line + 1, bottomRightFirst = line;
		result = max(result, go(1, 1, bottomRightFirst, m) + 
								go (topLeftSecond, 1, n, m));
	}

	for (int line = 1; line < m; line++) {
		int bottomRightFirst = line, topLeftSecond = line + 1;
		result = max(result, go(1, 1, n, bottomRightFirst) + 
								go (1, topLeftSecond, n, m));
	}
	fout << result;
	return 0;
}