Cod sursa(job #816237)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 17 noiembrie 2012 12:24:37
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 210;

int n, m, smax[N], antS[N], s[N], u, d[N][N], rez, cs[N], cd[N];
char a[N][N], b[N][N];

void calc() {
	int i, j, k;
	
	for(i = 1; i<=n; ++i)
		for(j = 1; j<=m; ++j)
			d[i][j] = (a[i][j] == '1' ? 0 : d[i - 1][j] + 1);
	
	for(i = 1; i <= n; ++i) {
		s[0] = 0;
		u = 0;
		for(j = 1; j<=m; ++j) {
			while(u && d[i][s[u]] >= d[i][j])
				--u;
			
			s[++u] = j;
			cs[j] = s[u - 1] + 1;
		}
		u = 0;
		
		antS[i] = antS[i - 1];
		s[0] = m + 1;
		
		for(j = m; j; --j) {
			while(u && d[i][s[u]] >= d[i][j])
				--u;
			
			s[++u] = j;
			cd[j] = s[u - 1] - 1;
			
			antS[i] = max(antS[i], (cd[j] - cs[j] + 1) * d[i][j]);
			
			//for(k = 1; k<=d[i][j]; ++k)
				//rez = max(rez, (cd[j] - cs[j] + 1) * k + antS[i - k]);
		}
	}
	
	for(i = n; i; --i)
		for(j = 1; j<=m; ++j) {
			d[n + 1][j] = 0;
			d[i][j] = (a[i][j] == '1' ? 0 : d[i + 1][j] + 1);
		}
	
		for(i = 1; i <= n; ++i) {
		s[0] = 0;
		u = 0;
		for(j = 1; j<=m; ++j) {
			while(u && d[i][s[u]] >= d[i][j])
				--u;
			
			s[++u] = j;
			cs[j] = s[u - 1] + 1;
		}
		u = 0;
		
		antS[i] = antS[i - 1];
		s[0] = m + 1;
		
		for(j = m; j; --j) {
			while(u && d[i][s[u]] >= d[i][j])
				--u;
			
			s[++u] = j;
			cd[j] = s[u - 1] - 1;
			
			rez = max(rez, antS[i - 1] + (cd[j] - cs[j] + 1) * d[i][j]);
			//for(k = 1; k<=d[i][j]; ++k)
				//rez = max(rez, (cd[j] - cs[j] + 1) * k + antS[i - k]);
		}
	}
}

int main() {
	int i, j;
	
	freopen("bmatrix.in", "r", stdin);
	freopen("bmatrix.out", "w", stdout);
	
	cin >> n >> m;
	cin.get();
	
	for(i = 1; i<=n; ++i)
		cin.getline(a[i] + 1, N);
	
	calc();
	
	for(i = 1; i<=max(n, m); ++i)
		for(j = 1; j<=max(m, n); ++j)
			b[i][j] = a[j][i];
	swap(n, m);
	for(i = 1; i<=n; ++i)
		for(j = 1; j<=m; ++j)
			a[i][j] = b[i][j];
	calc();
	
	cout << rez;
	
	return 0;
}