Cod sursa(job #2576076)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 6 martie 2020 17:10:11
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.12 kb
#include <fstream>
#include <stack>

using namespace std;

ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");

stack<int> s;
int m,n,v[505][505],st[505],dr[505],h[505],d1[505],d2[505],d3[505],d4[505],rasp;

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s;
		for(int j=0;j<m;j++){
			v[i][j+1]=s[j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(v[i][j]==0){
				h[j]++;
			}
			else
				h[j]=0;
		}
		while(s.size()>0){
			s.pop();
		}
		for(int j=1;j<=m;j++){
			while(s.size()>0 && h[j]<=h[s.top()]){
				s.pop();
			}
			if(s.size()==0){
				st[j]=0;
			}
			else{
				st[j]=s.top();	
			}
			s.push(j);
		}
		while(s.size()>0){
			s.pop();
		}
		for(int j=m;j>0;j--){
			while(s.size()>0 && h[j]<=h[s.top()]){
				s.pop();
			}
			if(s.size()==0){
				dr[j]=m+1;
			}
			else{
				dr[j]=s.top();	
			}
			s.push(j);
		}
		for(int j=1;j<=m;j++){
			d1[i]=max(d1[i],max(h[j],(dr[j]-st[j]-1)*h[j]));
		}
	}
	for(int i=1;i<=m;i++){
		h[i]=0;
	}
	while(s.size()>0){
		s.pop();
	}
	rasp=0;
	
	for(int i=n;i>0;i--){
		for(int j=1;j<=m;j++){
			if(v[i][j]==0){
				h[j]++;
			}
			else
				h[j]=0;
		}
		while(s.size()>0){
			s.pop();
		}
		for(int j=1;j<=m;j++){
			while(s.size()>0 && h[j]<=h[s.top()]){
				s.pop();
			}
			if(s.size()==0){
				st[j]=0;
			}
			else{
				st[j]=s.top();	
			}
			s.push(j);
		}
		while(s.size()>0){
			s.pop();
		}
		for(int j=m;j>0;j--){
			while(s.size()>0 && h[j]<=h[s.top()]){
				s.pop();
			}
			if(s.size()==0){
				dr[j]=m+1;
			}
			else{
				dr[j]=s.top();	
			}
			s.push(j);
		}
		for(int j=1;j<=m;j++){
			d2[i]=max(d2[i],max(h[j],(dr[j]-st[j]-1)*h[j]));
		}
	}
	for(int i=1;i<=m;i++){
		h[i]=0;
	}
	while(s.size()>0){
		s.pop();
	}
	rasp=0;
	
	
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(v[j][i]==0){
				h[j]++;
			}
			else
				h[j]=0;
		}
		while(s.size()>0){
			s.pop();
		}
		for(int j=1;j<=n;j++){
			while(s.size()>0 && h[j]<=h[s.top()]){
				s.pop();
			}
			if(s.size()==0){
				st[j]=0;
			}
			else{
				st[j]=s.top();	
			}
			s.push(j);
		}
		while(s.size()>0){
			s.pop();
		}
		for(int j=n;j>0;j--){
			while(s.size()>0 && h[j]<=h[s.top()]){
				s.pop();
			}
			if(s.size()==0){
				dr[j]=n+1;
			}
			else{
				dr[j]=s.top();	
			}
			s.push(j);
		}
		for(int j=1;j<=n;j++){
			d3[i]=max(d3[i],max(h[j],(dr[j]-st[j]-1)*h[j]));
		}
	}
	for(int i=1;i<=n;i++){
		h[i]=0;
	}
	while(s.size()>0){
		s.pop();
	}
	rasp=0;
	
	
	for(int i=m;i>0;i--){
		for(int j=1;j<=n;j++){
			if(v[j][i]==0){
				h[j]++;
			}
			else
				h[j]=0;
		}
		while(s.size()>0){
			s.pop();
		}
		for(int j=1;j<=n;j++){
			while(s.size()>0 && h[j]<=h[s.top()]){
				s.pop();
			}
			if(s.size()==0){
				st[j]=0;
			}
			else{
				st[j]=s.top();	
			}
			s.push(j);
		}
		while(s.size()>0){
			s.pop();
		}
		for(int j=n;j>0;j--){
			while(s.size()>0 && h[j]<=h[s.top()]){
				s.pop();
			}
			if(s.size()==0){
				dr[j]=n+1;
			}
			else{
				dr[j]=s.top();	
			}
			s.push(j);
		}
		for(int j=1;j<=n;j++){
			d4[i]=max(d4[i],max(h[j],(dr[j]-st[j]-1)*h[j]));
		}
	}
	
	rasp=0;
	for(int i=1;i<=n;i++){
		rasp=max(rasp,d1[i]+d2[i+1]);
	}
	for(int i=1;i<=m;i++){
		rasp=max(rasp,d3[i]+d4[i+1]);
	}
	cout<<rasp;
	return 0;
}