Cod sursa(job #65863)

Utilizator alextheroTandrau Alexandru alexthero Data 13 iunie 2007 15:38:24
Problema BMatrix Scor 92
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <stdio.h>

#define nmax 205

int sol,n,m,i,j,k,l[nmax][nmax],lin_jos[nmax],lin_sus[nmax],col_st[nmax],col_dr[nmax],lung;
char a[nmax][nmax];

inline int max(int a,int b) {
	return a > b ? a : b;
}

inline int min(int a,int b) {
	return a > b ? b : a;
}

int main() {
	freopen("bmatrix.in","r",stdin);
	freopen("bmatrix.out","w",stdout);

	scanf("%d%d\n",&n,&m);
	for(i = 1; i <= n; i++) {
		for(j = 1; j <= m; j++) scanf("%c",&a[i][j]);
		scanf("\n");
	}

	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			l[i][j] = (a[i][j] == '0') ? l[i][j - 1] + 1 : 0;

	for(i = 1; i <= n; i++) 
		for(j = 1; j <= m; j++) {
			lin_sus[i] = max(lin_sus[i],l[i][j]);
			lung = l[i][j];
			for(k = i - 1; k >= 1; k--) {
				lung = min(lung,l[k][j]);
				lin_sus[i] = max(lin_sus[i],(i - k + 1) * lung);
			}
		}

	for(i = n; i >= 1; i--) 
		for(j = 1; j <= m; j++) {
			lin_jos[i] = max(lin_jos[i],l[i][j]);
			lung = l[i][j];
			for(k = i + 1; k <= n; k++) {
				lung = min(lung,l[k][j]);
				lin_jos[i] = max(lin_jos[i],(k - i + 1) * lung);
			}
		}

	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			l[i][j] = (a[i][j] == '0') ? l[i - 1][j] + 1 : 0;

	for(j = 1; j <= m; j++)
		for(i = 1; i <= n; i++) {
			col_st[j] = max(col_st[j],l[i][j]);
			col_dr[j] = max(col_dr[j],l[i][j]);
			lung = l[i][j];
			for(k = j - 1; k >= 1; k--) {
				lung = min(lung,l[i][k]);
				col_st[j] = max(col_st[j],(j - k + 1) * lung);
			}
			lung = l[i][j];
			for(k = j + 1; k <= m; k++) {
				lung = min(lung,l[i][k]);
				col_dr[j] = max(col_dr[j],(k - j + 1) * lung);
			}
		}

	for(i = 1; i <= n; i++) lin_sus[i] = max(lin_sus[i - 1],lin_sus[i]);
	for(i = n; i >= 1; i--) lin_jos[i] = max(lin_jos[i + 1],lin_jos[i]);
	for(i = 1; i <= m; i++) col_st[i] = max(col_st[i - 1],col_st[i]);
	for(i = m; i >= 1; i--) col_dr[i] = max(col_dr[i - 1],col_dr[i]);

	sol = 0;
	for(i = 1; i <= n; i++) sol = max(sol,lin_sus[i] + lin_jos[i + 1]);
	for(i = 1; i <= m; i++) sol = max(sol,col_st[i] + col_dr[i + 1]);

	printf("%d\n",sol);

	return 0;
}