Cod sursa(job #1310505)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 6 ianuarie 2015 22:11:26
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<fstream>
using namespace std;
int n, m, i, j, maxim, nr, ii, jj;
char a[202][202];
int s[202][202], sus[202], jos[202];
int maxi(int a, int b){
	if(a > b){
		return a;
	}
	else{
		return b;
	}
}
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int main(){
	fin>> n >> m;
	for(i = 1; i <= n; i++){
		for(j = 1; j <= m; j++){
			fin>> a[i][j];
			a[i][j] -= '0';
		}
	}
	for(i = 1; i <= n; i++){
		for(j = 1; j <= m; j++){
			s[i][j] = s[i-1][j] + a[i][j];
		}
	}
	for(ii = 1; ii <= n; ii++){
		for(i = ii; i <= n; i++){
			nr = 0;
			for(j = 1; j <= m; j++){
				if(s[i][j] - s[ii-1][j] == 0){
					nr++;
					sus[i] = maxi(sus[i], nr * (i - ii + 1));
					jos[ii] = maxi(jos[ii], nr * (i - ii + 1));
				}
				else{
					nr = 0;
				}
			}
		}
	}
	for(i = 2; i <= n; i++){
		sus[i] = maxi(sus[i], sus[i-1]);
	}
	for(i = n - 1; i >= 1; i--){
		jos[i] = maxi(jos[i], jos[i+1]);
	}
	for(i = 1; i <= n; i++){
		maxim = maxi(maxim, sus[i] + jos[i+1]);
	}
	for(i = 1; i <= n; i++){
		sus[i] = 0;
		jos[i] = 0;
		for(j = 1; j <= m; j++){
			s[i][j] = 0;
		}
	}
	for(i = 1; i <= n; i++){
		for(j = 1; j <= m; j++){
			s[i][j] = s[i][j-1] + a[i][j];
		}
	}
	for(jj = 1; jj <= m; jj++){
		for(j = jj; j <= m; j++){
			nr = 0;
			for(i = 1; i <= n; i++){
				if(s[i][j] - s[i][jj-1] == 0){
					nr++;
					sus[j] = maxi(sus[j], nr * (j - jj + 1));
					jos[jj] = maxi(jos[jj], nr * (j - jj + 1));
				}
				else{
					nr = 0;
				}
			}
		}
	}
	for(j = 2; j <= m; j++){
		sus[j] = maxi(sus[j], sus[j-1]);
	}
	for(j = m - 1; j >= 1; j--){
		jos[j] = maxi(jos[j], jos[j+1]);
	}
	for(j = 1; j <= m; j++){
		maxim = maxi(maxim, sus[j] + jos[j+1]);
	}
	fout<< maxim;
	return 0;
}