Cod sursa(job #1226699)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 6 septembrie 2014 21:36:23
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <stack>
#define DIM 1005

using namespace std;

ifstream f("dreptpal.in");
ofstream g("dreptpal.out");

int n, m;

int A[DIM][DIM], P[DIM][DIM];

stack<int> s;

inline int maxim(int x, int y) {
	return ( x>y ? x : y );
}

inline int minim(int x, int y) {
	return (x<y ? x : y);
}

int main() {
	f >> m >> n;
	for (int i = 1; i <= m; ++i)
	for (int j = 1; j <= n; ++j)
		f >> A[i][j];
	
	//MANACHER
	for (int i = 1; i <= m; ++i) {
		int R = 0, C = 0;
		for (int j = 1; j <= n - 1; ++j) {
			int j_mirror = 2 * C - j;
			P[i][j] = R > j ? minim(R - j, P[i][j_mirror]) : 0;
			while (j - P[i][j] - 1 > 0 && A[i][j - P[i][j] - 1] == A[i][j + P[i][j] + 1])
				++P[i][j];
			if (R < j + P[i][j]) {
				R = j + P[i][j];
				C = j;
			}
		}
	}
	
	int L, R;
	int SOL = 0;
	for (int j = 1; j <= n; ++j) {
		while (!s.empty())
			s.pop();
		for (int i = 1; i <= m + 1; ++i) {
			while (!s.empty() && P[i][j] <= P[s.top()][j]) {
				int head = s.top();
				s.pop();
				if (s.empty())
					L = 1;
				else
					L = s.top() + 1;
				R = i - 1;
				SOL = maxim(SOL, (R - L + 1)*(P[head][j]*2 + 1));
			}
			s.push(i);
		}
	}
	g << SOL;
	return 0;
}