Cod sursa(job #1939938)

Utilizator lflorin29Florin Laiu lflorin29 Data 26 martie 2017 10:53:16
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;

const int nMax = 1002;

int n, m, a[nMax][nMax];
int dp[nMax][nMax];
int st[nMax], dr[nMax];

void Cit(int &x) {
	x = 0;
	char c = getchar();

	while (!isdigit(c))
		c = getchar();

	while (isdigit(c)) {
		x = x * 10 + c - '0';
		c = getchar();
	}
}
int main() {
	freopen("dreptpal.in", "r", stdin);
	freopen("dreptpal.out", "w", stdout);
Cit( n);
Cit (m);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			Cit(a[j][i]);

	swap(n, m);

	for (int i = 1; i <= m; ++i) {
		int c = 0;

		for (int j = 1; j <= n; ++j) {
			dp[j][i] = max(1, min(dp[c][i] + c - j, dp[2 * c - j][i]));

			int &nr = dp[j][i];

			while (j + nr <= n && j - nr >= 1 && a[j + nr][i] == a[j - nr][i])
				++nr;

			if (j + dp[j][i] > c + dp[c][j])
				c = j;

		}
	}


	stack<int>s;
	int ans = 0;

	for (int i = 1; i <= n; ++i) {

		for (int j = 1; j <= m; ++j) {
			st[j] = j;
			dr[j] = j;
		}

		s = stack<int>();

		for (int j = 1; j <= m; ++j) {
			while (!s.empty() && dp[i][s.top()] >= dp[i][j])
				s.pop();

			if (s.empty())
				st[j] = 1;
			else st[j] = s.top() + 1;

			s.push(j);
		}

		s = stack<int>();

		for (int j = m; j; --j) {
			while (!s.empty() && dp[i][s.top()] >= dp[i][j])
				s.pop();

			if (s.empty())dr[j] = m;
			else dr[j] = s.top() - 1;

			s.push(j);
		}

		for (int j = 1; j <= m; ++j) {
			int dif = (dr[j] - st[j] + 1);

			int v = dif * (2 * dp[i][j] - 1);
			ans = max(ans, v);
		}
	}

	printf("%d\n", ans);
	return 0;
}