Cod sursa(job #1787976)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 25 octombrie 2016 13:08:19
Problema BMatrix Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstring>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <stack>
#include <bitset>
#define MOD 8192
#define pb push_back
#define INF 0x3f3f3f3f
#define ll long long
#define NMAX 205

using namespace std;

typedef pair<int, int> pii;

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

char v[NMAX][NMAX], aux[NMAX][NMAX];
int histograma[NMAX],stiva[NMAX],n,m;

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

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

			while(vf>0 && histograma[stiva[vf]]>histograma[j]) {
				area=histograma[stiva[vf]]*(j-stiva[vf]);
				maxarea=max(maxarea,area);
				--vf;
			}

			if(vf==0) maxarea=max(maxarea,histograma[j]);
			stiva[++vf]=j;
		}
		v[i][m+1]=0;
	}

	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;++i)
		res=max(res,solve(1,i)+solve(i+1,n));

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

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

	fout<<res;

	return 0;
}