Cod sursa(job #637606)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 20 noiembrie 2011 15:33:22
Problema DreptPal Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 1.42 kb
#include<stdio.h>

#define fsize 7000000
#define maxn 1005

FILE*f=fopen("dreptpal.in","r");
FILE*g=fopen("dreptpal.out","w");

int n,m,i,j,ch,lenght,p,u,arie,best,vf;
int A[maxn][maxn],D[maxn][maxn],D2[maxn][maxn],St[maxn];
char buff[fsize];

inline int next () {
	int r = 0;
	while ( buff[ch] >= '0' && buff[ch] <= '9' && ch <= lenght ){
		r = r * 10 + buff[ch] - '0';
		++ch;
	}
	++ch;
	return r;
}

int main () {
	
	
	lenght = fread(buff+1,1,fsize-5,f); ch = 1;
	n = next(); m = next();
	
	for ( i = 1 ; i <= n ; ++i ){
		for ( j = 1 ; j <= m ; ++j ){
			A[i][j] = next();
		}
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		for ( j = 1 ; j <= m ; ++j ){
			p = u = j;
			while ( 1 ){
				if ( !p || u > m || A[i][p] != A[i][u] )	break ;
				if ( D[i][j] < u - p + 1 )
					D[i][j] = u - p + 1;
				--p; ++u;
			}
		}
	}
	
	for ( i = 1;  i <= n  ;++i ){
		for ( j = 1 ; j <= m ; ++j ){
			D2[i][j] = D[j][i];
		}
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		
		for ( j = 1 , vf = 0 ; j <= m ; ++j ){
			p = St[vf];
			
			while ( vf && D[i][j] < D[i][ St[vf] ] ){
				arie = D[i][ St[vf] ] * ( p - St[vf-1] );
				best = best > arie ? best : arie;
				--vf;
			}
			
			St[++vf] = j;
		}
		
		for ( p = St[vf] ; vf ; --vf ){
			arie = D[i][ St[vf] ] * ( p - St[vf-1] );
			best = best > arie ? best : arie;
		}
		
	}
	
	fprintf(g,"%d\n",best);
	
	fclose(f);
	fclose(g);
	
	return 0;
}