Cod sursa(job #2606144)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 27 aprilie 2020 08:57:12
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
//#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("dreptpal.in");
ofstream cout("dreptpal.out");

const int NMAX = 1000;

int N, M;
int a[NMAX + 2][NMAX + 2], manacher[NMAX + 2][NMAX + 2];

void Manacher(int l)
{
	int drMax = 0, posDrMax = 0;

	for(int i = 1; i <= M; i++)
		if(i > drMax)
		{
			int st = i - 1, dr = i + 1;

			while(st >= 1 && dr <= M && a[l][st] == a[l][dr])
				st--, dr++;

			st++, dr--;

			manacher[l][i] = dr - i;
			drMax = dr, posDrMax = i;
		}
		else
		{
			if(i + manacher[l][2 * posDrMax - i] < drMax)
				manacher[l][i] = manacher[l][2 * posDrMax - i];
			else
				{
					int st = 2 * i - drMax, dr = drMax; 
					
					while(st >= 1 && dr <= M && a[l][st] == a[l][dr])
						st--, dr++;

					st++, dr--;

					manacher[l][i] = dr - i;
					drMax = dr, posDrMax = i;
				}
		}
}

int ans;
vector <int> pos[NMAX + 5];
int dad[NMAX + 5], sz[NMAX + 5];

int Root(int node)
{
	if(node == dad[node]) return node;
	return dad[node] = Root(dad[node]);
}

void dojoin(int l, int r, int val)
{
	l = Root(l);
	r = Root(r);

	if(l != r)
		{
			if(sz[l] > sz[r])
			{
				dad[r] = l;
				sz[l] += sz[r];

				ans = max(ans, sz[l] * (2 * val  + 1));
			}
			else
			{
				dad[l] = r;
				sz[r] += sz[l];
				
				ans = max(ans, sz[r] * (2 * val + 1));
			}
		}
}

void join(int col, int line, int val)
{
	if(manacher[line - 1][col] >= manacher[line][col])
		dojoin(line - 1, line, val);

	if(manacher[line + 1][col] >= manacher[line][col])
		dojoin(line + 1, line, val);
}

int main()
{
	cin >> N >> M;

	for(int i = 1; i <= N; i++)
		for(int j = 1; j <= M; j++)
			cin >> a[i][j];

	for(int i = 1; i <= N; i++)
		Manacher(i);
	
	/*
	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= M; j++)
			cout << manacher[i][j] << ' ';
		cout << '\n';
	}
	*/

	for(int col = 1; col <= M; col++)
		{
			for(int line = 1; line <= N; line++)
				{
					pos[line].clear();
					dad[line] = line;
					sz[line] = 1;
				}

			for(int line = 1; line <= N; line++)
				pos[manacher[line][col]].push_back(line);
			
			for(int val = M; val >= 1; val--)
				for(auto line : pos[val])
					join(col, line, val);
		}	

	cout << ans << '\n';

	return 0;
}