Cod sursa(job #1310089)

Utilizator mariusn01Marius Nicoli mariusn01 Data 6 ianuarie 2015 13:59:10
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
#include <iostream>

#define DIM 203

using namespace std;

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

int a[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);
			}
		}
	
	for (i=2;i<=n;i++)
		sus[i] = max(sus[i], sus[i-1]);
		
	for (i=n-1;i>=1;i--)
		jos[i] = max(jos[i], jos[i+1]);
}


/*
void afisare(char a[DIM][DIM], int n, int m) {
	int i, j;
	for (i=1;i<=n;i++) {
		for (j=1;j<=m;j++)
			cout<<a[i][j];
		cout<<"\n";
	}
	cout<<"\n";

}
*/

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

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

	//afisare(s, n, m);

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

	return 0;
}