Cod sursa(job #635820)

Utilizator FlorianFlorian Marcu Florian Data 19 noiembrie 2011 15:01:17
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 1.05 kb
using namespace std;
#include<fstream>
const int MAX_N = 1003;
int A[MAX_N][MAX_N], N, M;
int lg[MAX_N][MAX_N];
int sol = 1;
void solve(int j)
{
	int st[MAX_N], vf = 0;
	int l[MAX_N], r[MAX_N];
	int i;
	st[0] = 0;
	for( i = 1; i <= N; ++i )
	{
		while( vf && lg[i][j] <= lg[st[vf]][j] ) --vf;
		l[i] = st[vf] + 1;
		st[++vf] = i;
	}
	st[0] = N+1; vf = 0;
	for( i = N; i; --i )
	{
		while(vf && lg[i][j] <= lg[st[vf]][j] ) --vf;
		r[i] = st[vf] - 1;
		st[++vf] = i;
	}
	int cst = 1;
	for(i = 1; i <= N; ++i )
	{
		int tmp = lg[i][j] * (r[i] - l[i] + 1);
		if( tmp > cst ) cst = tmp;
	}
	if(sol < cst ) sol = cst;
}
int main()
{
	ifstream in("dreptpal.in"); ofstream out("dreptpal.out");
	in >> N >> M;
	int i, j, k;
	for(i = 1; i <= N; ++i )
		for(j = 1; j <= M; ++j )
			in >> A[i][j];
	for(i = 1; i <= N; ++i)
		for(j = 1; j <= M; ++j )
		{
			lg[i][j] = 1;
			k = 1;
			while( j + k <= M && j - k > 0 && A[i][j-k] == A[i][j+k] ) lg[i][j] += 2, ++k;
		}
	for(j = 1; j <= M; ++j )
		solve(j);
	out << sol << "\n";
	return 0;
}