Cod sursa(job #2634613)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 11 iulie 2020 17:49:45
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 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];
int stanga[205],dreapta[205];
int n,m,cnt;
int rotating[205][205];

void rotator()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			rotating[j][n-i+1]=a[i][j];
		}
	}
    swap(n,m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m+1;j++)
			a[i][j]=rotating[i][j];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<a[i][j];
		cout<<"\n";
	}
}


void solve(int dir)
{
	for(int i=1;i<=204;i++)
		h[i]=0;
	while (cnt) cnt--;
	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;
		}
		while (cnt) cnt--;
		stiva[0]=0;
		cnt=0;
		for(int j=1;j<=m;j++)
		{
			while(cnt>0 && h[stiva[cnt]]>=h[j])
				cnt--;
			stanga[j]=stiva[cnt];
			stiva[++cnt]=j;
		}
		stiva[0]=m+1;
		cnt=0;
		for(int j=m;j>=1;j--)
		{

			while(cnt>0 && 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()
{
    int unu=0,zero=0;
	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<=n;i++)
    {
        int ok=0;
        for(int j=1;j<=m;j++)
            if(a[i][j]==1) ok++;
        if(ok==0) zero++;
        else if(ok==m) unu++;
    }
    if(unu+zero==n)
    {
        out<<(n-1)*m;
        return 0;
    }
	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;
}