Cod sursa(job #1310480)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 6 ianuarie 2015 21:46:42
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include<fstream>
using namespace std;
int n, m, i, j, u, maxim, maxim1, maxim2, x, k;
int s[202][202], c[201];
char a[201][201];
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++){
			if(a[i][j] == 1){
				s[i][j] = 0;
			}
			else{
				s[i][j] = s[i-1][j] + 1;
			}
		}
	}
	for(k = 1; k < n; k++){
		maxim1 = 0;
		maxim2 = 0;
		for(i = 1; i <= k; i++){
			u = 1;
			c[1] = 1;
			for(j = 2; j <= m; j++){
				x = c[u];
				while(s[i][c[u]] > s[i][j]){
					if((x - c[u] + 1) * (s[i][c[u]]) > maxim1){
						maxim1 = (x - c[u] + 1) * (s[i][c[u]]);
					}
					u--;
				}
				u++;
				c[u] = j;
			}
			x = c[u];
			while(u > 0){
				if((x - c[u] + 1) * (s[i][c[u]]) > maxim1){
					maxim1 = (x - c[u] + 1) * (s[i][c[u]]);
				}
				u--;
			}
		}
		for(i = k + 1;  i <= n; i++){
			u = 1;
			c[1] = 1;
			for(j = 2; j <= m; j++){
				x = c[u];
				while(s[i][c[u]] > s[i][j]){
					if((x - c[u] + 1) * (s[i][c[u]]) > maxim2 && i - s[i][c[u]] > k){
						maxim2 = (x - c[u] + 1) * (s[i][c[u]]);
					}
					else{
						if((x - c[u] + 1) * (i - k) > maxim2){
							maxim2 = (x - c[u] + 1) * (i - k);
						}
					}
					u--;
				}
				u++;
				c[u] = j;
			}
			x = c[u];
			while(u > 0){
				if((x - c[u] + 1) * (s[i][c[u]]) > maxim2){
					maxim2 = (x - c[u] + 1) * (s[i][c[u]]);
				}
				u--;
			}
		}
		if(maxim1 + maxim2  > maxim){
			maxim = maxim1 + maxim2;
		}
	}
	for(k = 1; k < m; k++){
		maxim1 = 0;
		maxim2 = 0;
		for(i = 1; i <= n; i++){
			u = 1;
			c[1] = 1;
			for(j = 2; j <= k; j++){
				x = c[u];
				while(s[i][c[u]] > s[i][j]){
					if((x - c[u] + 1) * (s[i][c[u]]) > maxim1){
						maxim1 = (x - c[u] + 1) * (s[i][c[u]]);
					}
					u--;
				}
				u++;
				c[u] = j;
			}
			x = c[u];
			while(u > 0){
				if((x - c[u] + 1) * (s[i][c[u]]) > maxim1){
					maxim1 = (x - c[u] + 1) * (s[i][c[u]]);
				}
				u--;
			}
		}
		for(i = 1;  i <= n; i++){
			u = 1;
			c[1] = k + 1;
			for(j = k + 2; j <= m; j++){
				x = c[u];
				while(s[i][c[u]] > s[i][j]){
					if((x - c[u] + 1) * (s[i][c[u]]) > maxim2){
						maxim2 = (x - c[u] + 1) * (s[i][c[u]]);
					}
					u--;
				}
				u++;
				c[u] = j;
			}
			x = c[u];
			while(u > 0){
				if((x - c[u] + 1) * (s[i][c[u]]) > maxim2){
					maxim2 = (x - c[u] + 1) * (s[i][c[u]]);
				}
				u--;
			}
		}
		if(maxim1 + maxim2  > maxim){
			maxim = maxim1 + maxim2;
		}
	}
	fout<< maxim;
	return 0;
}