Cod sursa(job #2634194)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 10 iulie 2020 01:14:34
Problema BMatrix Scor 96
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

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

int h[205];
char a[205][205];
int b[5][205],stiva[205],cnt;
int stanga[205],dreapta[205];
int n,m;

void rotator()
{
	int rotate[205][205];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			rotate[j][n-i+1]=a[i][j];
		}
	}
	swap(n,m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=rotate[i][j];
}


void solve(int dir)
{
	for(int i=1;i<=204;i++)
		h[i]=0;
	for(int i=1;i<=n;i++)
	{
		b[dir][i]=b[dir][i-1];
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='0')
				h[j]=h[j]+1;
			else
				h[j]=0;
		}
		stiva[0]=0;
		cnt=0;
		for(int j=1;j<=m;j++)
		{
			while(cnt && h[stiva[cnt]]>=h[j])
				cnt--;
			stanga[j]=stiva[cnt];
			stiva[++cnt]=j;
		}
		stiva[0]=m+1;
		cnt=0;
		for(int j=m;j>0;j--)
		{

			while(cnt && h[stiva[cnt]]>=h[j])
				cnt--;
			dreapta[j]=stiva[cnt];
			stiva[++cnt]=j;
		}
		for(int j=1;j<=m;j++)
		{
			if(b[dir][i]<h[j]*(dreapta[j]-stanga[j]-1))
				b[dir][i]=h[j]*(dreapta[j]-stanga[j]-1);
		}
	}
}


int main()
{
	in>>n>>m;
	for(int i=1;i<+n;i++)
		for(int j=1;j<=m;j++)
			in>>a[i][j];
	for(int i=1;i<=4;i++)
	{
		solve(i);
		rotator();
	}
	int sol=0;
	for(int i=1;i<=n;i++)
	{
		sol=max(sol,b[1][i]+b[3][n-i]);
	}
	for(int i=1;i<=m;i++)
	{
		sol=max(sol,b[2][i]+b[4][m-i]);
	}
	out<<sol;
	return 0;
}