Cod sursa(job #2633136)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 6 iulie 2020 16:13:08
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

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

int mat[201][201],h[201];
int sus[201],jos[201],stanga[201],dreapta[201];
/*void rotate(int n,int m)
{
	int rotate[201][201];
	int ct=m;
	for(int i=1;i<=n;i++)
	{
		int ii=1;
		for(int j=1;j<=m;j++)
		{
			rotate[i][j]=a[ii][ct];
			ii++;
		}
		ct--;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=rotate[i][j];
	swap(n,m);
}*/

int main()
{
	int n,m;
	in>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			in>>mat[i][j];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(mat[i][j]==0) h[j]++;
			else h[j]=0;
			int a=1999999999,b=0;
			for(int k=j;k>=1;k--)
			{
				a=min(a,h[k]);
				b=max(b,a*(j-k+1));
			}
			stanga[i]=max(stanga[i],max(stanga[i-1],b));
			sus[i]=max(sus[i],max(sus[i-1],b));
		}
	}
	for(int i=1;i<=201;i++)
		h[i]=0;
	for(int i=n;i>=1;i--)
		for(int j=m;j>=1;j--)
		{
			if(mat[i][j]==0) h[j]++;
			else h[j]==0;
			int a=1999999999,b=0;
			for(int k=j;k<=m;k++)
			{
				a=min(a,h[k]);
				b=max(b,a*(k-j+1));
			}
			dreapta[i]=max(dreapta[i],max(dreapta[i+1],b));
			jos[i]=max(jos[i],max(jos[i+1],b));
		}
	int sol=0;
	for(int i=1;i<n;i++)
		sol=max(sol,stanga[i]+dreapta[i+1]);
	for(int i=1;i<m;i++)
		sol=max(sol,sus[i]+jos[i+1]);
	out<<sol;
	return 0;
}