Cod sursa(job #775777)

Utilizator maritimCristian Lambru maritim Data 8 august 2012 21:10:22
Problema BMatrix Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<stdio.h>
#include<fstream>
using namespace std;

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

#define MaxN 210

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

void citire(void)
{
	int a = 0;
	
	f >> N >> M;
	f.getline(S,40100,EOF);
	for(int i=0;S[i];i++)
		if(isdigit(S[i]))
		{
			++ a; 
			for(int j=0;isdigit(S[i]);A[a][++j] = S[i++]-'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=c1;i<=c2;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] = c2+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/2+1;i++)
		Sol = max(Sol,SubMatMax(1,i,1,M)+SubMatMax(i+1,N,1,M));
	
	for(int i=1;i<=M/2+1;i++)
		Sol = max(Sol,SubMatMax(1,N,1,i)+SubMatMax(1,N,i+1,M));
}

int main()
{
	citire();
	Rezolvare();
	
	g << Sol << "\n";
}