Cod sursa(job #3300894)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 19 iunie 2025 19:47:53
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<cstdio>
#include<algorithm>
constexpr int NMAX=1024;

int N, M;
char mat[NMAX][NMAX];
int up[NMAX][NMAX];
int down[NMAX][NMAX];
int U[NMAX];
int D[NMAX];
int l[NMAX], r[NMAX];
int ans;

void calc()
{
	int i, j;

	for(j=0;j<M;++j)
		up[0][j]=(mat[0][j]=='0');
	for(i=1;i<N;++i)
		for(j=0;j<M;++j)
			up[i][j]=(mat[i][j]=='0' ? up[i-1][j]+1 : 0);

	for(j=0;j<M;++j)
		down[N-1][j]=(mat[N-1][j]=='0');
	for(i=N-2;i>-1;--i)
		for(j=0;j<M;++j)
			down[i][j]=(mat[i][j]=='0' ? down[i+1][j]+1 : 0);

	for(i=0;i<N;++i)
	{
		for(j=0;j<M;++j)
			for(l[j]=j-1;l[j]>-1 && up[i][l[j]]>=up[i][j];l[j]=l[l[j]]);
		for(j=M-1;j>-1;--j)
			for(r[j]=j+1;r[j]<M && up[i][r[j]]>=up[i][j];r[j]=r[r[j]]);

		for(U[i]=j=0;j<M;++j)
			U[i]=std::max(U[i], up[i][j]*(r[j]-l[j]-1));
	}
	for(i=1;i<N;++i)
		U[i]=std::max(U[i], U[i-1]);

	for(i=0;i<N;++i)
	{
		for(j=0;j<M;++j)
			for(l[j]=j-1;l[j]>-1 && down[i][l[j]]>=down[i][j];l[j]=l[l[j]]);
		for(j=M-1;j>-1;--j)
			for(r[j]=j+1;r[j]<M && down[i][r[j]]>=down[i][j];r[j]=r[r[j]]);

		for(D[i]=j=0;j<M;++j)
			D[i]=std::max(D[i], down[i][j]*(r[j]-l[j]-1));
	}
	for(i=N-2;i>-1;--i)
		D[i]=std::max(D[i], D[i+1]);

	for(i=1;i<N;++i)
		ans=std::max(ans, U[i-1]+D[i]);
}

int solve()
{
	int i, j;

	calc();
	for(i=1;i<std::max(N, M);++i)
		for(j=0;j<i;++j)
			std::swap(mat[i][j], mat[j][i]);
	std::swap(N, M);
	calc();

	return ans;
}

int main()
{
	FILE* f=fopen("bmatrix.in", "r"), *g=fopen("bmatrix.out", "w");
	// FILE* f=stdin, *g=stdout;
	int i;

	fscanf(f, "%d%d", &N, &M);
	fgets(mat[0], NMAX, f);
	for(i=0;i<N;++i)
		fgets(mat[i], NMAX, f);

	fprintf(g, "%d\n", solve());

	fclose(f);
	fclose(g);
	return 0;
}