Cod sursa(job #635420)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 19 noiembrie 2011 11:21:07
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 1.25 kb
#include<cstdio>
#include<deque>
#include<utility>
using namespace std;

int n,m,i,j,k,l,ok,sol,q,L[1010],pal(int,int);

deque<pair<int, pair<int,int> > > Q;

void read(),solve();

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("dreptpal.in","r",stdin);
	freopen("dreptpal.out","w",stdout);
	scanf("%d%d",&n,&m);
}

void solve()
{
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%d",&L[j]);
		}
		q=Q.size();
		for(k=1;k<=m-2;k++)
		{
			for(l=k+2;l<=m;l+=2)
			{
				if(pal(k,l))
				{
					ok=0;
					for(deque<pair<int, pair<int,int> > >::iterator it=Q.begin();it!=Q.begin()+q;it++)
					{
						pair<int,pair<int,int> > curr=*it;
						if(curr.second.first==k && curr.second.second==l)
						{
							Q.push_back(make_pair(curr.first+1,make_pair(k,l)));
							if((l-k+1)*(curr.first+1)>sol)sol=(l-k+1)*(curr.first+1);
							ok=1;
							break;
						}
					}
					if(!ok)
					{
						Q.push_back(make_pair(1,make_pair(k,l)));
						if(l-k+1>sol)sol=l-k+1;
					}
				}
			}
		}
		for(;q--;)Q.pop_front();
	}
	if(sol<n)sol=n;
	printf("%d\n",sol);
}

int pal(int beg,int end)
{
	while(beg<end)
	{
		if(L[beg]==L[end]){beg++;end--;}
		else return 0;
	}
	
	return 1;
}