Cod sursa(job #824550)

Utilizator toranagahVlad Badelita toranagah Data 26 noiembrie 2012 18:59:02
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <iostream>
using namespace std;
const int MAX_N = 201;
bool mat[MAX_N][MAX_N];
int row[MAX_N];
struct {
	int h, l;
} st[MAX_N];
int stTop;
int N, M;
int result;

void read();
void solve();
void print();

int main() {
	read();
	solve();
	print();
}

void read() {
	ifstream fin("bmax.in");
	fin >> N >> M;
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			fin >> mat[i][j];
		}
	}
	for (int i = 0; i <= M; ++i) {
		row[i] = 0;
	}
	st[0].l = st[0].h = -1;
}

void solve() {
	result = 0;
	for (int i = 1; i <= N; ++i) {
		stTop = 0;
		st[stTop].h = -1;
		for (int j = 1; j <= M; ++j) {
			if (mat[i][j] == true) {
				row[j] = 0;
				while (stTop > 0) {
					if (st[stTop].h * (j - st[stTop].l) > result {
						result = st[stTop]
					}
				}
			} else {
				++row[j];
			}
			int l;
			while (row[j] <= st[stTop].h) {
				st[stTop].l;
				--stTop;
			}
			st[++stTop].h = row[j];
			st[stTop].l = l > 0 ? l : j;
		}
		while (stTop > 0) {

		}
	}
}

void print() {
	ofstream fout("bmax.out");
	fout << result;
}