Cod sursa(job #2694240)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 8 ianuarie 2021 15:37:09
Problema BMatrix Scor 36
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
//------------------------------------------------
///Globale
const int NMAX = 202;
int n,m,v[NMAX][NMAX],rasp,rasp2,d[NMAX][NMAX],d2[NMAX][NMAX],dp[NMAX],dp2[NMAX],st[NMAX],v2[NMAX][NMAX];
//------------------------------------------------
///Functii
void citire();
void rezolvare();
void afisare();
//------------------------------------------------
int main()
{
	citire();
	rezolvare();
	afisare();
	return 0;
}
//------------------------------------------------
void afisare()
{
	g << max(rasp,rasp2);
}
//------------------------------------------------
void roteste()
{
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
		{
			v2[j][i] = v[i][j];
			v[i][j] = 0;
		}
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			v[i][j] = v2[i][j];
}
//------------------------------------------------
void curata()
{
	for(int i = 0; i < NMAX; ++i)
		for(int j = 0; j < NMAX; ++j)
		{
			d[i][j] = 0;
			d2[i][j] = 0;
		}
	for(int j = 0; j < NMAX; ++j)
	{
		dp[j] = 0;
		dp2[j] = 0;
	}
}
//------------------------------------------------
int calculeaza(int n,int m)
{
	int r = 0,nr = 0;
	curata();
	for(int j = 1; j <= m; ++j)
	{
		nr = 0;
		dp[j] = dp[j - 1];
		for(int i = 1; i <= n; ++i)
		{
			if(v[i][j] == 0)
				d[i][j] = d[i][j - 1] + 1;
			else
				d[i][j] = 0;
			while(nr > 0 && d[i][j] <= d[st[nr]][j])
				nr--;
			dp[j] = max(dp[j],d[i][j] * (i - st[nr]));
			nr++;
			st[nr] = i;
		}
	}
	for(int j = m; j >= 1; --j)
	{
		nr = 0;
		dp2[j] = dp2[j + 1];
		for(int i = 1; i <= n; ++i)
		{
			if(v[i][j] == 0)
				d2[i][j] = d2[i][j + 1] + 1;
			else
				d2[i][j] = 0;
			while(nr > 0 && d2[i][j] <= d2[st[nr]][j])
				nr--;
			dp2[j] = max(dp2[j],d2[i][j] * (i - st[nr]));
			nr++;
			st[nr] = i;
			r = max(r,dp2[j] + dp[j - 1]);
		}
	}
	return r;
}
//------------------------------------------------
void rezolvare()
{
	rasp = calculeaza(n,m);
	roteste();
	rasp2 = calculeaza(m,n);
}
//------------------------------------------------
void citire()
{
	f >> n >> m;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
		{
			char c;
			f >> c;
			if(c == '1')
				v[i][j] = 1;
		}
}