Cod sursa(job #775740)

Utilizator maritimCristian Lambru maritim Data 8 august 2012 20:04:23
Problema BMatrix Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>

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

#define MaxN 210

int N,M,Sol;
int A[MaxN][MaxN];
char S[MaxN];
int St[MaxN],P[MaxN],D[MaxN];

void citire(void)
{
	fscanf(f,"%d %d\n",&N,&M);
	for(int i=1;i<=N;i++)
	{
		fgets(S,sizeof(S),f);
		for(int j=0;S[j];j++)
			A[i][j+1] = S[j]-'0';
	}
}

inline int max(int a,int b)
{
	return a > b ? a : b;
}

inline int SubMatMax(int l1,int l2,int c1,int c2)
{
	int pf = 0,Sol = 0;
	
	for(int i=0;i<=M;i++)
		D[i] = St[i] = P[i] = 0;
	P[0] = c1-1;
	
	for(int i=l1;i<=l2;i++)
	{
		for(int j=c1;j<=c2;j++)
			if(A[i][j] == 0)
			{
				for(;St[pf] >= D[j]+1 && pf; --pf);
				St[++pf] = D[j]+1; P[pf] = j;
				Sol = max(Sol,St[pf]*(j-P[pf-1]));
			}
			else
				pf = 0,D[j] = 0,P[0] = j;
		
		pf = 0;
		P[0] = c1-1;
		
		for(int j=c2;j>=c1;j--)
			if(A[i][j] == 0)
			{
				++ D[j];
				for(;St[pf] >= D[j] && pf;--pf);
				St[++pf] = D[j]; P[pf] = j;
				Sol = max(Sol,St[pf]*(P[pf-1]-j));
			}
			else
				pf = 0,P[0] = j;
	}
	
	return Sol;
}

void Rezolvare(void)
{
	for(int i=1;i<N;i++)
		Sol = max(Sol,SubMatMax(1,i,1,M)+SubMatMax(i+1,N,1,M));
	
	for(int i=1;i<M;i++)
		Sol = max(Sol,SubMatMax(1,N,1,i)+SubMatMax(1,N,i+1,M));
}

int main()
{
	citire();
	Rezolvare();
	
	fprintf(g,"%d\n",Sol);
}