Cod sursa(job #2332596)

Utilizator patcasrarespatcas rares danut patcasrares Data 30 ianuarie 2019 21:35:44
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int DN=205;
int n,m;
char a[DN][DN],b[DN][DN];
int dp[4][DN][DN],ma,lg[DN][DN],nr,val,cnt[DN][DN],f,lst[DN];
void solve()
{
    for(int i=0;i<=n+1;i++)
		for(int j=0;j<=m+1;j++)
            lg[i][j]=dp[0][i][j]=dp[1][i][j]=cnt[i][j]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='1')
				continue;
			lg[i][j]=1+lg[i-1][j];
		}
	for(int type=0;type<2;type++)
	{
	for(int i=1;i<=n;i++)
		//for(int h=1;h<=i;h++)
		{
			nr=0;
			for(int j=1;j<=m;j++)
			{
				if(lg[i][j]==0)
					continue;
				f=j-1;
				while(lg[i][f]>=lg[i][j])
					f=lst[f];
				lst[j]=f;
				cnt[i][j]=j-f;
			}
			lg[i][m+1]=0;
			for(int j=m;j>0;j--)
			{
				if(lg[i][j]==0)
					continue;
				f=j+1;
				while(lg[i][f]>=lg[i][j])
					f=lst[f];
				lst[j]=f;
				cnt[i][j]+=f-j-1;
			}

			for(int j=1;j<=m;j++)
			{
				if(lg[i][j]==0)
					continue;
				int h=i-lg[i][j]+1;
				dp[type][i][j]=max(dp[type][i][j],cnt[i][j]*lg[i][j]);
			}
		}
		for(int i=n;i>0;i--)
		for(int j=1;j<=m;j++)
		{
			lg[i][j]=0;
			if(a[i][j]=='1')
				continue;
			lg[i][j]=1+lg[i+1][j];
		}
	}
	f=0;
	for(int i=n;i>0;i--)
	{
		for(int j=1;j<=m;j++)
			f=max(f,dp[1][i+1][j]);
		for(int j=1;j<=m;j++)
			ma=max(ma,dp[0][i][j]+f);
	}
}
int main()
{
	fin>>n>>m;
	for(int i=0;i<=n;i++)
		fin.getline(a[i]+1,DN);
	solve();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			b[j][i]=a[i][j];
	swap(n,m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=b[i][j];
	solve();
	fout<<ma;
}