Cod sursa(job #2678799)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 28 noiembrie 2020 18:31:26
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <string>
using namespace std;

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

bool b[201][201];
int s[201][201];

int dpf(int n, int m)
{
	int i, j, k, rasp = 0, lg, lgmax;
	int dp[201] = {};
	
	for (i = 1; i<=n; i++)
		for (j = 1; j<=m; j++)
			s[i][j] = s[i-1][j] + b[i][j];
	
	for (i = 1; i<=n; i++)
	{
		dp[i] = max(dp[i], dp[i-1]);
		for (j = i; j<=n; j++)
		{
			lg = lgmax = 0;
			for (k = 1; k<=m; k++)
			{
				if (s[j][k] - s[i-1][k] == 0)
					lg++;
				else
				{
					lgmax = max(lg, lgmax);
					lg = 0;
				}
			}
			lgmax = max(lgmax, lg);
			rasp = max(rasp, lgmax*(j-i+1) + dp[i-1]);
			dp[j] = max(dp[j], lgmax*(j-i+1));
		}
	}
	return rasp;
}

int main()
{
	int n, m, i, j, x;
	int rasp;
	string str;
	
	fin >> n >> m;
	for (i = 1; i<=n; i++)
	{
		fin >> str;
		for (j = 1; j<=m; j++)
			b[i][j] = str[j-1] - '0';
	}
	rasp = dpf(n, m);
	x = max(n, m);
	for (i = 1; i<=x; i++)
		for (j = 1; j<=x; j++)
			s[i][j] = b[j][i];
	swap(n, m);
	for (i = 1; i<=n; i++)
		for (j = 1; j<=m; j++)
			b[i][j] = s[i][j];
	
	fout << max(rasp, dpf(n, m));
	return 0;
}