Cod sursa(job #1405255)

Utilizator vladrochianVlad Rochian vladrochian Data 28 martie 2015 23:23:41
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <stack>
using namespace std;

const int kMaxN = 1005;

int N, M, ans;
int a[kMaxN][kMaxN], best[kMaxN][kMaxN];

void Read() {
	ifstream fin("dreptpal.in");
	fin >> N >> M;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			fin >> a[i][j];
}

void Manacher() {
	for (int i = 1; i <= N; ++i) {
		int right = 0, mid;
		for (int j = 1; j <= M; ++j) {
			if (j <= right)
				best[i][j] = min(right - j, best[i][mid - (j - mid)]);
			while (j - best[i][j] > 1 && j + best[i][j] < M && a[i][j - best[i][j] - 1] == a[i][j + best[i][j] + 1])
				++best[i][j];
			if (j + best[i][j] > right) {
				right = j + best[i][j];
				mid = j;
			}
		}
	}
}

void Solve() {
	stack<pair<int, int>> st;
	for (int i = 1; i <= M; ++i) {
		for (int j = 1; j <= N; ++j) {
			int start = j;
			while (!st.empty() && st.top().first >= best[j][i]) {
				start = min(start, st.top().second);
				ans = max(ans, (st.top().first * 2 + 1) * (j - start));
				st.pop();
			}
			st.emplace(best[j][i], start);
		}
		int start = N + 1;
		while (!st.empty()) {
			start = min(start, st.top().second);
			ans = max(ans, (st.top().first * 2 + 1) * (N + 1 - start));
			st.pop();
		}
	}
}

int main() {
	Read();
	Manacher();
	Solve();
	ofstream("dreptpal.out") << ans << "\n";
	return 0;
}