Cod sursa(job #1431249)

Utilizator theprdvtheprdv theprdv Data 9 mai 2015 06:05:30
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <algorithm>

using namespace std;

fstream fin("bmatrix.in", ios::in);
fstream fout("bmatrix.out", ios::out);

#define MAXN 2005
char A[MAXN][MAXN];
int X[MAXN][MAXN], up[MAXN], dw[MAXN], M, N, sol;

void solve(bool P){
	for (int i = 1; i <= M; ++i){
		for (int j = 1; j <= N; ++j)
			X[i][j] = (1 - (A[P ? i : N - j + 1][P ? j : i] - '0')) * (X[i - 1][j] + 1);
		up[i] = dw[i] = 0;
	}
	for (int i = 1; i <= M; ++i){
		for (int j = i; j <= M; ++j){
			int w = 0;
			for (int k = 1; k <= N; ++k)
				if (X[j][k] >= j - i + 1){
					++w;
					up[j] = max(up[j], w * (j - i + 1));
					dw[i] = max(dw[i], w * (j - i + 1));
				}
				else w = 0;
		}
		up[i] = max(up[i], up[i - 1]);
		dw[M - i + 1] = max(dw[M - i + 1], dw[M - i + 2]);
	}
	for (int i = 1; i <= M; i++)
		sol = max(sol, up[i] + dw[i + 1]);
}

int main(){
	fin >> M >> N;
	for (int i = 1; i <= M; ++i)
		fin >> A[i] + 1;

	solve(true);
	swap(M, N);
	solve(false);
	fout << sol;
	
	fin.close();
	fout.close();
	return 0;
}