Cod sursa(job #2332420)

Utilizator patcasrarespatcas rares danut patcasrares Data 30 ianuarie 2019 18:51:36
Problema BMatrix Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 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];
void solve()
{
	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];
			dp[0][i][j]=dp[1][i][j]=0;
		}
	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]<i-h+1)
				{
					nr=0;
					cnt[i][j]=0;
					continue;
				}
				nr++;
				cnt[i][j]=nr;
			}
			nr=0;
			for(int j=m;j>0;j--)
			{
				if(lg[i][j]<i-h+1)
				{
					nr=0;
					cnt[i][j]=0;
					continue;
				}
				nr++;
				cnt[i][j]+=nr-1;
			}
			for(int j=1;j<=m;j++)
			{
				dp[0][i][j]=max(dp[0][i][j],cnt[i][j]*(i-h+1));
				dp[1][h][j]=max(dp[1][h][j],cnt[i][j]*(i-h+1));
			}
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ma=max(ma,dp[0][i][j]+dp[1][i+1][j]);
}
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;
}