Cod sursa(job #2227582)

Utilizator shantih1Alex S Hill shantih1 Data 1 august 2018 06:16:17
Problema BMatrix Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <cmath>

using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

int x,y,mx,i,j,nr,MX;
int n[210][210],e[210][210],s[210][210],v[210][210],lv[210],lh[210];
bool o[210][210];
string g;
struct cod
{	int x, id;	};
stack<cod> q;

int update (int x,int l,int mx)
{
	while(!q.empty()&&x<q.top().x)
	{
		mx=max(mx, q.top().x*abs(l-q.top().id));
		q.pop();
	}
	if(x)	q.push({x,l});
	return mx;
}

int main () {
    
    fin>>x>>y;
	getline(fin, g);
	for(i=1;i<=x;i++)
	{
		getline(fin, g);
		for(j=0;j<g.size();j++)
			o[i][j+1]=g[j]-'0';
	}
	
	for(i=1;i<=x;i++)
	{
		for(j=1;j<=y;j++)
			if(o[i][j]==0)	v[i][j]=v[i][j-1]+1;
		for(j=y;j>=1;j--)
			if(o[i][j]==0)	e[i][j]=e[i][j+1]+1;
	}
	for(j=1;j<=y;j++)
	{
		for(i=1;i<=x;i++)
			if(o[i][j]==0)	n[i][j]=n[i-1][j]+1;
		for(i=x;i>=1;i--)
			if(o[i][j]==0)	s[i][j]=s[i+1][j]+1;
	}
	
	mx=0;
	for(i=1;i<=x;i++)
	{
		for(j=1;j<=y+1;j++)
			mx=update(n[i][j],j,mx);
		for(j=y;j>=0;j--)
			mx=update(n[i][j],j,mx);
		lh[i]+=mx;
	}

	mx=0;
	for(i=x;i>1;i--)
	{
		for(j=1;j<=y+1;j++)
			mx=update(s[i][j],j,mx);
		for(j=y;j>=0;j--)
			mx=update(s[i][j],j,mx);
		lh[i-1]+=mx;
	}
	
	mx=0;
	for(j=1;j<=y;j++)
	{
		for(i=1;i<=x+1;i++)
			mx=update(v[i][j],i,mx);
		for(i=x;i>=0;i--)
			mx=update(v[i][j],i,mx);
		lv[j]+=mx;
	}
	
	mx=0;
	for(j=y;j>1;j--)
	{
		for(i=1;i<=x+1;i++)
			mx=update(e[i][j],i,mx);
		for(i=x;i>=0;i--)
			mx=update(e[i][j],i,mx);
		lv[j-1]+=mx;
	}
	
	for(i=1;i<=x;i++)
		if(lh[i]>MX)	MX=lh[i];
	for(i=1;i<=y;i++)
		if(lv[i]>MX)	MX=lv[i];
	
	fout<<MX<<"\n";
    //n-am reusit...
	//un an mai tarziu
}