Cod sursa(job #635426)

Utilizator HakunaMatataA.A.A. HakunaMatata Data 19 noiembrie 2011 11:28:42
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 1.84 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;

inline 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;
}

inline bool try_sol( int pos1, int pos2 )
{
	if( (pos2&1) != (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;
	}

	if( try_sol( pos1+1, pos2-1 )==true )
	{
		add_sol( pos1,pos2 );
		return true;
	}

	return false;
}

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

char AA[NMAX*10];

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

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

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

	for(i=1; i<=N; ++i)
	{
		CLine=i;
		fgets( AA, NMAX*10, stdin );
		p=-1;

		for(j=1; j<=M; ++j)
		{
			a1=0;
			for( ++p; AA[p]!=' ' && AA[p]!='\n'; ++p )
			{
				a1*=10;
				a1+=AA[p]-'0';
			}

			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( (l1&1) == (l2&1) ) 
				{
					try_sol(l1,l2);
				}
			}
		}
	}

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