Cod sursa(job #1310068)

Utilizator mariusn01Marius Nicoli mariusn01 Data 6 ianuarie 2015 13:42:51
Problema BMatrix Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>

#define DIM 203

using namespace std;

char s[DIM][DIM];
int a[DIM][DIM], b[DIM][DIM];

int sus[DIM], jos[DIM];

int n, m, i, j, sol, nr;

void calcul() {
	int i, j, k, aria;
	
	
	for (i=1;i<=n;i++) {
		for (j=1;j<=m;j++)
			if (s[i][j] == '0')
				a[i][j] = 1 + a[i-1][j];
			else
				a[i][j] = 0;
		sus[i] = jos[i] = 0;
	}
	for (i=1;i<=n;i++)
		for (j=i;j<=n;j++) {
			nr = 0;
			for (k=1;k<=m;k++) {
				if (a[j][k] >= j-i+1)
					nr++;
				else
					nr=0;
				aria = nr * (j-i+1);
				sus[j] = max(sus[j], aria);
				jos[i] = max(jos[i], aria);
			}
		}
	

}

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

int main() {
	fin>>n>>m;
	for (i=1;i<=n;i++) {
		fin>>s[i] + 1;
	}

	calcul();
	for (i=1;i<n;i++)
		sol = max(sol, sus[i] + jos[i+1]);
		
		
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			b[m-j+1][i] = a[i][j];
			
	swap(n, m);
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			a[i][j] = b[i][j];
	
	calcul();
	for (i=1;i<n;i++)
		sol = max(sol, sus[i] + jos[i+1]);
	
	fout<<sol;		

	return 0;
}