Submission #1606089

---

Source Code Expand

#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
 
#define INFLL 2000000000000000000
#define INF 2000000000
#define MOD 1000000007
#define PI acos(-1.0)
 
using namespace std;
 
typedef pair <int, int> pii;

bool isGood[2000][2000];
bool board[2000][2000];
int up[2000][2000];
int n, m;
int ll[2000], rr[2000];
int curRow;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); j++) {
			board[i][j] = (str[j] == '#');
		}
	}
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m - 1; j++) {
			int cnt = 0;
			for (int x = 0; x < 2; x++)
				for (int y = 0; y < 2; y++)
					if (board[i + x][j + y])
						cnt++;
			if (cnt % 2 == 0)
				isGood[i][j] = true;
			else
				isGood[i][j] = false;
		}
	}
	m--;
	n--;
	for (int i = 0; i < m; i++) 
		if (isGood[0][i]) up[0][i] = 1;
		else up[0][i] = 0;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (isGood[i][j])
				up[i][j] = up[i - 1][j] + 1;
			else
				up[i][j] = 0;
		}
	}
	int ans = max(n + 1, m + 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			ll[j] = rr[j] = j;
		stack <int> st;
		st.push(-1);
		for (int j = 0; j < m; j++) {
			while (st.top() != -1 && up[i][st.top()] >= up[i][j]) st.pop();
			ll[j] = st.top();
			st.push(j);
		}
		st = stack <int>();
		st.push(m);
		for (int j = m - 1; j >= 0; j--) {
			while (st.top() != m && up[i][st.top()] >= up[i][j]) st.pop();
			rr[j] = st.top();
			st.push(j);
		}
		for (int j = 0; j < m; j++) {
			if (up[i][j] == 0)
				continue;
			ans = max(ans, (rr[j] - ll[j]) * (up[i][j] + 1));
			//cout << i << " " << j << " " << ll[j] << " " << rr[j] << endl;
		}
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result