Cod sursa(job #2184766)

Utilizator stefantagaTaga Stefan stefantaga Data 24 martie 2018 11:09:43
Problema BMatrix Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

int m,n,dr[205],st[205],sus[205],jos[205],fr[205],i,j,maxim,x,y,k;char v[205][205];
int inf=INT_MAX;
int main()
{

    f>>n>>m;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            f>>v[i][j];
        }
    }
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            if (v[i][j]=='0')
            {
                fr[j]++;
            }
            else
            {
                fr[j]=0;
            }
            x=inf;
        y=0;
        for (k=j;k>=1;k--)
        {
            x=min(fr[k],x);
            y=max(y,x*(j-k+1));
        }
        st[i]=max(st[i],max(st[i-1],y));
        sus[j]=max(sus[j],max(sus[j-1],y));
        }

    }
    memset(fr,0,sizeof(fr));
     for (i=n;i>=1;i--)
    {
        for (j=m;j>=1;j--)
        {
            if (v[i][j]=='0')
            {
                fr[j]++;
            }
            else
            {
                fr[j]=0;
            }
            x=inf;
        y=0;
        for (k=j;k<=m;k++)
        {
            x=min(fr[k],x);
            y=max(y,x*(k-j+1));
        }
        dr[i]=max(dr[i],max(dr[i+1],y));
        jos[j]=max(jos[j],max(dr[j+1],y));
        }
    }
    maxim=0;
    for (i=1;i<n;i++)
    {
        maxim=max(maxim,st[i]+dr[i+1]);
    }
    for (j=1;j<m;j++)
    {
        maxim=max(maxim,sus[j]+jos[j+1]);
    }
    g<<maxim;
    return 0;
}