Cod sursa(job #822229)

Utilizator Marius96Marius Gavrilescu Marius96 Data 23 noiembrie 2012 00:10:11
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<cstdio>
#include<stack>
#include<algorithm>
using std::stack;
using std::max;
using std::min;

struct str
{
	int s,h;
	
	str()
		{
			s=h=0;
		}

	str (int ss,int hh)
		{
			s=ss;
			h=hh;
		}
};

static int v[205][205];
static stack<struct str> st;
static int h[205];
static int mxa,mxb;

static void calcaltpeste (int j1,int j2)
{
	mxa=0;
	mxb=0;
	for(int j=j1;j<j2;j++){
		int p=j;
		while(st.empty()||st.top().h!=h[j]){
			if(st.empty()||st.top().h<h[j])
				st.push (str (p,h[j]));
			else if(st.top().h>h[j]){
				int xx=st.top().h;
				int yy=j-st.top().s;
				if(yy*xx>mxa*mxb){
					mxa=xx;
					mxb=yy;
				}
				p=st.top().s;
				st.pop();
			}
		}
	}

	while(!st.empty()){
		int xx=st.top().h;
		int yy=j2-st.top().s;
		if(xx*yy>mxa*mxb)
			mxa=xx,mxb=yy;
		st.pop();
	}
}

static int calcpeste (int i1,int j1,int i2,int j2)
{
	for(int j=j1;j<j2;j++)
		h[j]=!v[i1][j];

	int mmxa=0,mmxb=0;
	for(int l=i1;l<i2;){
		calcaltpeste (j1,j2);
		l++;
		for(int j=j1;j<j2;j++)
			if(v[l][j])
				h[j]=0;
			else
				h[j]++;

		if(mxa*mxb>mmxa*mmxb)
			mmxa=mxa,mmxb=mxb;
	}

	return mmxa*mmxb;
}

int main()
{
	freopen ("bmatrix.in","r",stdin);
#ifdef INFOARENA
	freopen ("bmatrix.out","w",stdout);
#endif

	int m,n;
	scanf ("%d%d",&m,&n);
	for(int i=0;i<m;i++){
		scanf (" ");
		for(int j=0;j<n;j++)
			v[i][j]=getchar()-'0';
	}

	int mx=0;
	for(int i=1;i<=min (m/2+1,m-1);i++){
		int c=calcpeste (0,0,i,n)+calcpeste (i,0,m,n);
		if(c>mx)
			mx=c;
	}

	for(int i=1;i<=min (n/2+1,n-1);i++){
		int c=calcpeste (0,0,m,i)+calcpeste (0,i,m,n);
		if(c>mx)
			mx=c;
	}

	printf ("%d",mx);
	return 0;
}