Cod sursa(job #777268)

Utilizator maritimCristian Lambru maritim Data 11 august 2012 18:23:11
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 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++)
	{
		pf = 0;
		
		for(int j=c1;j<=c2;j++)
			if(A[i][j] == 0)
			{
				++ D[j];
				
				if(St[pf] < D[j] || !pf)
					St[++pf] = D[j], P[pf] = j;
				else
				{
					for(;St[pf] > D[j] && pf; --pf)
						Sol = max(Sol,St[pf]*(j-P[pf]));
					if(St[pf] < D[j] || !pf)
						St[++pf] = D[j];
				}
			}
			else
			{
				for(;pf; --pf)
					Sol = max(Sol,St[pf]*(j-P[pf]));
			}
			
		for(;pf; --pf)
			Sol = max(Sol,St[pf]*(c2-P[pf]+1));
	}
	
	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";
}