Cod sursa(job #3295236)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 3 mai 2025 18:26:44
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
int max_sum;
void check(int n, int m, int v[205][205] ){
	int dp_sus[205] = { 0 }, dp_jos[205] = { 0 }, h[205] = { 0 }, st[205] = { 0 }, dr[205] = { 0 }, i, j;
	for( i = 1; i <= n; i++ ){
		vector <int> s;
		for( j = 1; j <= m; j++ ){
			if( v[i][j] == 1 ){
				h[j] = 0;
			}
			else{
				h[j]++;
			}
		}
		h[0] = -1;
		s.push_back( 0 );
		for( j = 1; j <= m; j++ ){
			while( h[s.back()] >= h[j] ){
				s.pop_back();
			}
			st[j] = s.back();
			s.push_back( j );
		}
		s.clear();
		h[m + 1] = -1;
		s.push_back( m + 1 );
		dp_sus[i] = dp_sus[i - 1];
		for( j = m; j >= 1; j-- ){
			while( h[s.back()] >= h[j] ){
				s.pop_back();
			}
			dr[j] = s.back();
			s.push_back( j );
			//cout << st[j] << ' ' << dr[j] << '\n';
			dp_sus[i] = max( dp_sus[i], h[j] * ( dr[j] - st[j] - 1 ) );
		}
		//cout << dp_sus[i] << '\n';
	}
	for( i = 1; i <= m; i++ ){
		h[i] = 0;
	}
	for( i = n; i >= 1; i-- ){
		vector <int> s;
		for( j = 1; j <= m; j++ ){
			if( v[i][j] == 1 ){
				h[j] = 0;
			}
			else{
				h[j]++;
			}
		}
		h[0] = -1;
		s.push_back( 0 );
		for( j = 1; j <= m; j++ ){
			while( h[s.back()] >= h[j] ){
				s.pop_back();
			}
			st[j] = s.back();
			s.push_back( j );
		}
		s.clear();
		h[m + 1] = -1;
		s.push_back( m + 1 );
		dp_jos[i] = dp_jos[i + 1];
		for( j = m; j >= 1; j-- ){
			while( h[s.back()] >= h[j] ){
				s.pop_back();
			}
			dr[j] = s.back();
			s.push_back( j );
			dp_jos[i] = max( dp_jos[i], h[j] * ( dr[j] - st[j] - 1 ) );
		}
		max_sum = max( dp_sus[i - 1] + dp_jos[i], max_sum );
	}
}
int main(){
	int a[205][205], b[205][205];
	int n, m, i, j;
	char c;
	ifstream fin( "bmatrix.in" );
	ofstream fout( "bmatrix.out" );
	fin >> n >> m;
	for( i = 1; i <= n; i++ ){
		for( j = 1; j <= m; j++ ){
			fin >> c;
			a[i][j] = b[j][i] = c - '0';
		}
	}
	max_sum = 0;
	check( n, m, a );
	check( m, n, b );
	fout << max_sum;
	return 0;
}