Cod sursa(job #1790147)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 27 octombrie 2016 20:45:01
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>

using namespace std;

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

char v[205][205], aux[205][205];
int hist[205],stiva[205],n,m;

int solve(int sus, int jos) {
	int i,j,maxarea=0,vf=0,top;

	for(i=1;i<=m+1;++i) hist[i]=0;
	for(i=sus;i<=jos;++i) {
		vf=1;
		for(j=1;j<=m+1;++j) {
			if(v[i][j]=='1') hist[j]=0;
			else ++hist[j];

			if(j==m+1) hist[j]=0;

			top=stiva[vf-1];
			while(hist[stiva[vf-1]]>hist[j]) {
				maxarea=max(maxarea,hist[stiva[vf-1]]*(top-stiva[vf-2]));
				--vf;
			}
			stiva[vf++]=j;
		}
	}

	return maxarea;
}

int main() {
	int i,j,res=0;

	fin>>n>>m;
	for(i=1;i<=n;++i) fin>>(v[i]+1);

	for(i=1;i<=n/2;++i)
		res=max(res,solve(1,i)+solve(i+1,n));

	swap(n,m);
	for(int i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			aux[i][j]=v[j][i];
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			v[i][j]=aux[i][j];

	for(i=1;i<=n/2;++i)
		res=max(res,solve(1,i)+solve(i+1,n));

	fout<<res;

	return 0;
}