Cod sursa(job #1026500)

Utilizator andreiiiiPopa Andrei andreiiii Data 11 noiembrie 2013 18:11:54
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <algorithm>
#include <cstdio>
#include <stack>
#define N 202
#define INF 0x3f3f3f3f
using namespace std;

char a[2][N][N];
int dp[2][N][N], st[N], dr[N], sol[2][N];

int solve(int l, int n, int m)
{
	int i, j, ret=0;
	stack <int> s;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(a[l][i][j]=='0') dp[0][i][j]=dp[0][i-1][j]+1;
			else dp[0][i][j]=0;
		}
	}
	for(i=n;i;i--)
	{
		for(j=m;j;j--)
		{
			if(a[l][i][j]=='0') dp[1][i][j]=dp[1][i+1][j]+1;
			else dp[1][i][j]=0;
		}
	}
	for(i=1;i<=n;i++)
	{
		//sus
		sol[0][i]=sol[0][i-1];
		for(j=1;j<=m;j++)
		{
			while(!s.empty()&&dp[0][i][s.top()]>=dp[0][i][j])
			{
				dr[s.top()]=j-1;
				s.pop();
			}
			if(!s.empty()) st[j]=s.top()+1;
			else st[j]=1;
			s.push(j);
		}
		while(!s.empty())
		{
			dr[s.top()]=m;
			s.pop();
		}
		for(j=1;j<=m;j++) sol[0][i]=max(sol[0][i], dp[0][i][j]*(dr[j]-st[j]+1));
		//jos
		sol[1][i]=0;
		for(j=1;j<=m;j++)
		{
			while(!s.empty()&&dp[1][i][s.top()]>=dp[1][i][j])
			{
				dr[s.top()]=j-1;
				s.pop();
			}
			if(!s.empty()) st[j]=s.top()+1;
			else st[j]=1;
			s.push(j);
		}
		while(!s.empty())
		{
			dr[s.top()]=m;
			s.pop();
		}
		for(j=1;j<=m;j++) sol[1][i]=max(sol[1][i], dp[1][i][j]*(dr[j]-st[j]+1));
		ret=max(ret, sol[0][i-1]+sol[1][i]);
	}
	return ret;
}

int main()
{
	freopen("bmatrix.in", "r", stdin);
	freopen("bmatrix.out", "w", stdout);
	int n, m, i, j;
	scanf("%d %d\n", &n, &m);
	for(i=1;i<=n;i++)
	{
		fgets(a[0][i]+1, N+3, stdin);
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			a[1][j][i]=a[0][i][j];
		}
	}
	printf("%d\n", max(solve(0, n, m), solve(1, m, n)));
	//printf("%d %d", solve(0, n, m), solve(1, m, n));
}