Pagini recente » Cod sursa (job #1582422) | Cod sursa (job #1689713) | Cod sursa (job #1739553) | Cod sursa (job #3181608) | Cod sursa (job #635426)
Cod sursa(job #635426)
/*
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;
}