Cod sursa(job #635386)

Utilizator HakunaMatataA.A.A. HakunaMatata Data 19 noiembrie 2011 11:01:18
Problema DreptPal Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 1.6 kb
/*
	Brutty O( N^2*M )
*/

#include<stdio.h>
#include<algorithm>
using namespace std;

#define NMAX 1024
typedef struct{
	int CurrentStreak,
		lastline;
}Smen;

typedef struct{
	int poz,val;
}NType;

int A[NMAX][NMAX];
NType P[NMAX];
Smen S[NMAX][NMAX];

int CLine,ANS;

void add_sol( int pos1, int pos2 )
{
	int C = S[pos1][pos2].CurrentStreak;
	int ll= S[pos1][pos2].lastline;

	if( ll==CLine-1 )
	{
		C+=1;
		if( C*(pos2-pos1+1)>ANS )
			ANS=C*(pos2-pos1+1);
	}
	else
		C=1;

	ll=CLine;

	S[pos1][pos2].CurrentStreak=C;
	S[pos1][pos2].lastline=ll;

}

bool try_sol( int pos1, int pos2 )
{
	if( (pos2-pos1)&1 || A[CLine][pos1] != A[CLine][pos2] )
		return false;

	if( S[pos1][pos2].lastline==CLine )
		return true;

	if( pos2-pos1 == 2 || pos2==pos1 )
	{
		add_sol( pos1, pos2 );
		return true;
	}

	return try_sol( pos1+1, pos2-1 );
}


inline bool cmp( NType a, NType b )
{
	if( a.val==b.val )
		return a.poz<b.poz;
	return a.val < b.val;
}

int main()
{
	freopen("dreptpal.in","r",stdin);
	freopen("dreptpal.out","w",stdout);

	int N,M;
	scanf("%d%d",&N,&M);

	int i,j,a1,k;
	int lspos=-1,lstype=0;
	int l1,l2;
	ANS=N;

	for(i=1; i<=N; ++i)
	{
		CLine=i;

		for(j=1; j<=M; ++j)
		{
			scanf("%d",&a1);

			A[i][j]=a1;
			P[j].poz=j;
			P[j].val=a1;
		}

		sort( P+1, P+M+1, cmp );

		for(j=1; j<=M; ++j)
		{
			lstype=P[j].val;
			l1=P[j].poz;

			for(k=j+1; k<=M && P[k].val==lstype; ++k)
			{
				l2=P[k].poz;

				if( !((l2-l1)&1) ) 
				{
					try_sol(l1,l2);
				}
			}
		}
	}

	printf("%d\n",ANS);
	return 0;
}