Cod sursa(job #637145)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 20 noiembrie 2011 12:20:40
Problema DreptPal Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 0.9 kb
#include<cstdio>
#define Nmax 1024
using namespace std;

int N,M;

int a[Nmax][Nmax],m[Nmax][Nmax];


int main(){
	
	freopen("dreptpal.in","r",stdin);
	freopen("dreptpal.out","w",stdout);
	
	//citim matricea
	scanf("%d%d",&N,&M);
	
	for(int i=1;i<=N;++i)
		for(int j=1;j<=M;++j)
			scanf("%d",&a[i][j]);
		
	//gasim cele mai lungi palindroame de pe fiecare linie care se termina in poz j
		
	for(int p=1;p<=N;++p)
		for(int j=1;j<=M;++j){
			m[p][j]=1;
			for(int len=m[p][j-1];len>=1;--len)
			if(j!=1 && a[p][j] == a[p][j-len-1]){
				m[p][j]=len+2;
				break;
			}
	}
		
	//gasim aria maxima pt dreptunghiul care se termina in i,j
	
	int sol=0;
	
	for(int c=1;c<=M;++c)
		for(int i=1;i<=N;++i){
			int min=0x3f3f3f3f;
			for(int j=i;j<=N;++j){
				if(m[j][c] <min)
					min=m[j][c];
				if(min*(j-i+1) > sol)
					sol=min*(j-1+1);
			}
		}
	printf("%d",sol);
return 0;
}