Cod sursa(job #2941423)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 17 noiembrie 2022 19:00:32
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>
#define NMAX 203
#define MOD 555557

using namespace std;

int n, m;

char mat[NMAX][NMAX];

int dp[NMAX][NMAX];//dp[i][j] nr maxim de 0 de pe col j in sus
int sus[NMAX], jos[NMAX];//aria celui mai mare dreptunghi de deasupra i/ sub i

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

void solve() {

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= m; j++) {

			if (mat[i][j] == '0')
			{
				dp[i][j] = 1 + dp[i - 1][j];//cresc practic nr de 0 de pe col i
			}
			else
			{
				dp[i][j] = 0;//se reseteaza secv
			}
		}

		sus[i] = jos[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		//setez linia de sus
		for (int j = i; j <= n; j++) {
			//in j setez linia de jos a dreptunghiului
			int nr = 0;//numarul de coloane consecutive unde pot sa imi formez un dreptunghi
			for (int k = 1; k <= m; k++) {
				//in k am coloana dreptunghiului
				if (dp[j][k] >= j - i + 1)
				{
					
					nr++;
				}
				else
				{
					nr = 0;
				}

				int aria = nr * (j - i + 1);
				//reactualizez deasupra j 
				sus[j] = max(sus[j], aria);

				//reactualizez sub i
				jos[i] = max(jos[i], aria);
			}
		}
	}

	//iau maximul secvenntial din vectori
	for (int i = 2; i <= n; i++)
	{
		sus[i] = max(sus[i], sus[i - 1]);
	}


	for (int i = n - 1; i >= 1; i--)
	{
		jos[i] = max(jos[i], jos[i + 1]);
	}

}

int main()
{
	fin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		fin >> mat[i] + 1;
	}
	solve();

	int sol = 0;
	for (int i = 1; i <= n; i++)
	{

		sol = max(sol, jos[i + 1] + sus[i]);
	}
	fout << sol;
	return 0;
}