Cod sursa(job #1512648)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 28 octombrie 2015 14:00:44
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

void find_best_matrix_up(const vector<vector<bool> >& v, vector<int>& rez){
	const int n = v.size(), m = v[0].size();
	vector<int> adanc(m, 0), len_st(m, 0), st(n);
	rez.resize(n, 0);
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			adanc[j] = (v[i][j] ? 0 : adanc[j]+1); }
		st.clear();

		for(int j = 0; j < m; ++j){
			while(!st.empty() && adanc[st.back()] >= adanc[j]){
				st.pop_back(); }
			len_st[j] = (st.empty() ? j : j-st.back()-1);
			st.push_back(j); }

		
		rez[i] = (i == 0 ? 0 : rez[i-1]);

		st.clear();
		for(int j = m-1; j >= 0; --j){
			while(!st.empty() && adanc[st.back()] >= adanc[j]){
				st.pop_back(); }
			int len_dr = (st.empty() ? m-1-j : st.back()-j-1);
			rez[i] = max(rez[i], (len_st[j]+len_dr+1) * adanc[j]);
			st.push_back(j); } } }

template <typename V>
void print(const V v){
	for(const auto x : v){
		for(const auto y : x){
			cout << y;}
		cout << endl; }
	cout << endl; }


int main(){
	ifstream f("bmatrix.in");
	ofstream g("bmatrix.out");
	int n, m;
	f >> n >> m >> ws;
	vector<vector<bool> > v(n, vector<bool>(m, false)), inv_v(n, vector<bool>(m, false)),
		v_t(m, vector<bool>(n, false)), inv_v_t(m, vector<bool>(n, false));

	char buf[256];
	for(int i = 0; i < n; ++i){
		f.read(&buf[0], m);
		f.ignore();
		for(int j = 0; j < m; ++j){
			v[i][j] = inv_v[n-i-1][j] = v_t[j][i] = inv_v_t[m-j-1][i] = (buf[j] == '1'); } }
	vector<int> best_v, best_inv_v, best_v_t, best_inv_v_t;
	find_best_matrix_up(v, best_v);
	find_best_matrix_up(inv_v, best_inv_v);
	find_best_matrix_up(v_t, best_v_t);
	find_best_matrix_up(inv_v_t, best_inv_v_t);

	int best = 0;
	for(int i = 0; i+1 < n; ++i){
		best = max(best, best_v[i] + best_inv_v[n-i-2]); }
	for(int i = 0; i+1 < m; ++i){
		best = max(best, best_v_t[i] + best_inv_v_t[m-i-2]); }
	g << best;
	return 0; }