Cod sursa(job #637989)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 20 noiembrie 2011 17:59:58
Problema DreptPal Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 1.27 kb
#include<fstream>

#define maxn 1005

using namespace std;

ifstream f("dreptpal.in");
ofstream g("dreptpal.out");

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

int main () {
	
	f >> n >> m;
	for ( i = 1 ; i <= n ; ++i ){
		for ( j = 1 ; j <= m ; ++j ){
			f >> A[i][j];
		}
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		p = u = 1;
		for ( j = 1 ; j <= m ; ++j ){
			if ( j <= u ){
				D[i][j] = D[i][p+u-j] < u - j ? D[i][p+u-j] : u - j;
				if ( j + D[i][j] >= u ){
					p = j - D[i][j]; u = j + D[i][j];
					while ( p >= 2 && u <= m - 1 && A[i][p-1] == A[i][u+1] ){
						--p; ++u; ++D[i][j];
					}
				}
			}
			else{
				p = u = j;
				while ( p >= 2 && u <= m - 1 && A[i][p-1] == A[i][u+1] ){
					--p; ++u; ++D[i][j];
				}
			}
		}
		for ( j = 1 ; j <= m ; ++j ){
			D[i][j] = D[i][j] + D[i][j] + 1;
		}
	}
	
	for ( j = 1 ; j <= m ; ++j ){
		for ( vf = 0, i = 1 ; i <= n ; ++i ){
			p = St[vf];
			while ( vf && D[i][j] < D[St[vf]][j] ){
				arie = D[St[vf]][j] * ( p - St[vf-1] );
				if ( best < arie )	best = arie;
				--vf;
			}
			St[++vf] = i;
		}
		for ( p = St[vf] ; vf ; --vf ){
			arie = D[St[vf]][j] * ( p - St[vf-1] );
			if ( best < arie )	best = arie;
		}
	}
	
	g << best << "\n";
	
	f.close();
	g.close();
	
	return 0;
}