Cod sursa(job #750888)

Utilizator darrenRares Buhai darren Data 23 mai 2012 16:41:22
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <algorithm>

using namespace std;

int N, M;
int A[1002][1002], B[1002][1002];
int st[1002], lf[1002], rg[1002];
int maxarea;

int main()
{
	ifstream fin("dreptpal.in");
	ofstream fout("dreptpal.out");
	
	fin >> N >> M;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			fin >> A[i][j];
	for (int i = 1; i <= N; ++i)
	{
		int center = 0, last = 0;
		for (int j = 1; j <= M; ++j)
		{
			B[i][j] = 1;
			if (last > j)
				B[i][j] = B[i][center - (j - center)];
			while (j - B[i][j] / 2 > 1 && j + B[i][j] / 2 < M && A[i][j - B[i][j] / 2 - 1] == A[i][j + B[i][j] / 2 + 1])
				B[i][j] += 2;
			if (j + B[i][j] / 2 > last)
			{
				center = j;
				last = j + B[i][j] / 2;
			}
		}
	}
	
	for (int i = 1; i <= M; ++i)
	{
		st[0] = 0;
		for (int j = 1; j <= N; ++j)
		{
			while (st[0] && B[j][i] <= B[st[st[0]]][i])
				--st[0];
			if (!st[0]) lf[j] = j;
			else        lf[j] = j - st[st[0]];
			st[++st[0]] = j;
		}
		st[0] = 0;
		for (int j = N; j >= 1; --j)
		{
			while (st[0] && B[j][i] <= B[st[st[0]]][i])
				--st[0];
			if (!st[0]) rg[j] = N - j + 1;
			else        rg[j] = st[st[0]] - j;
			st[++st[0]] = j;
		}
		
		for (int j = 1; j <= N; ++j)
			maxarea = max(maxarea, B[j][i] * (lf[j] + rg[j] - 1));
	}
	
	fout << maxarea << '\n';
	
	fin.close();
	fout.close();
}