Cod sursa(job #878663)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 14 februarie 2013 17:34:20
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<fstream>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,sol;
char A[2][210][210];
int sus[210][210],jos[210][210],solsus[210],soljos[210];
int St[210],vf=-1,st[210],dr[210];

inline int Solve(int p,int n,int m)
{
	int i,j,rez=0;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(A[p][i][j]=='0')
				sus[i][j]=sus[i-1][j]+1;
			else
				sus[i][j]=0;
		}
	}
	for(i=n;i>0;i--)
	{
		for(j=m;j>0;j--)
		{
			if(A[p][i][j]=='0')
				jos[i][j]=jos[i+1][j]+1;
			else
				jos[i][j]=0;
		}
	}
	for(i=1;i<=n;i++)
	{
		solsus[i]=soljos[i]=0;
		for(j=1;j<=m;j++)
		{
			while(vf>=0 && sus[i][St[vf]]>=sus[i][j])
			{
				dr[St[vf]]=j-1;
				vf--;
			}
			if(vf>=0)
				st[j]=St[vf]+1;
			else
				st[j]=1;
			St[++vf]=j;
		}
		while(vf>=0)
		{
			dr[St[vf]]=m;
			vf--;
		}
		for(j=1;j<=m;j++)
			solsus[i]=max(max(solsus[i-1],solsus[i]),sus[i][j]*(dr[j]-st[j]+1));
		//
		for(j=1;j<=m;j++)
		{
			while(vf>=0 && jos[i][St[vf]]>=jos[i][j])
			{
				dr[St[vf]]=j-1;
				vf--;
			}
			if(vf>=0)
				st[j]=St[vf]+1;
			else
				st[j]=1;
			St[++vf]=j;
		}
		while(vf>=0)
		{
			dr[St[vf]]=m;
			vf--;
		}
		for(j=1;j<=m;j++)
			soljos[i]=max(soljos[i],jos[i][j]*(dr[j]-st[j]+1));
	}
	for(i=1;i<n;i++)
		rez=max(rez,solsus[i]+soljos[i+1]);
	return rez;
}

int main()
{
	int i,j;
	ifstream fin("bmatrix.in");
	fin>>n>>m;
	for(i=1;i<=n;i++)
		fin>>(A[0][i]+1);
	fin.close();
	
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			A[1][j][i]=A[0][i][j];
	sol=max(Solve(0,n,m),Solve(1,m,n));
	
	ofstream fout("bmatrix.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}