Cod sursa(job #972709)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 12 iulie 2013 14:52:17
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb

#include <cstdio>
#include <algorithm>

const int MAX_SIZE(1002);

int n, m, Result;
int Matrix [MAX_SIZE] [MAX_SIZE];
int Dp [MAX_SIZE] [MAX_SIZE];
int Stack [MAX_SIZE];

inline void Read (void)
{
	std::freopen("dreptpal.in","r",stdin);
	std::scanf("%d %d\n",&n,&m);
	int i, j;
	for (i = 1 ; i <= n ; ++i)
		for (j = 1 ; j <= m ; ++j)
			std::scanf("%d",&Matrix[i][j]);
	std::fclose(stdin);
}

inline void Print (void)
{
	std::freopen("dreptpal.out","w",stdout);
	std::printf("%d\n",Result);
	std::fclose(stdout);
}

inline void Manacher (int *v, int *dp)
{
	v[0] = -1;
	v[m + 1] = -2;
	int i, c(1), r(0), mirror;
	for (i = 1 ; i <= m ; ++i)
	{
		mirror = c - (i - c);
		dp[i] = std::min(dp[mirror],r - i);
		while (v[i + dp[i] + 1] == v[i - dp[i] - 1])
			++dp[i];
		if (i + dp[i] > r)
		{
			c = i;
			r = c + dp[c];
		}
	}
}

inline void Dynamic (void)
{
	int i;
	for (i = 1 ; i <= n ; ++i)
		Manacher(Matrix[i], Dp[i]);
}

inline void Compute (void)
{
	int i, j, top, left, right, length;
	for (j = 1 ; j <= m ; ++j)
	{
		top = 0;
		for (i = 1 ; i <= n + 1 ; ++i)
		{
			while (top > 0 && Dp[i][j] <= Dp[Stack[top]][j])
			{
				left = Stack[top - 1] + 1;
				right = i - 1;
				length = Dp[Stack[top]][j];
				Result = std::max(Result,(right - left + 1) * ((length << 1) + 1));
				--top;
			}
			Stack[++top] = i;
		}
	}
}

int main (void)
{
	Read();
	Dynamic();
	Compute();
	Print();
	return 0;
}