Cod sursa(job #2027012)

Utilizator KonoplyankaKonoplyanka Konoplyanka Data 25 septembrie 2017 14:41:50
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n,m,i,j,k,ult,fr[1<<8],D[1<<8],up[1<<8],down[1<<8],Left[1<<8],Right[1<<8];
char M[1<<8][1<<8];
int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i) f>>(M[i]+1);
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)
        {
            if(M[i][j]=='0') ++fr[j];
            else fr[j]=0;
            int nr=0,h=1<<30;;
            for(k=j;k>0;--k)
            {
                h=min(h,fr[k]);
                nr=max(nr,h*(j-k+1));
            }
            Left[i]=max(max(Left[i-1],Left[i]),nr);
            up[j]=max(max(up[j-1],up[j]),nr);
        }
    }
    for(i=1;i<=m;++i) fr[i]=0;
    for(i=n;i>0;--i)
    {
        for(j=m;j>0;--j)
        {
            if(M[i][j]=='0') ++fr[j];
            else fr[j]=0;
            int nr=0,h=1<<30;;
            for(k=j;k<=m;++k)
            {
                h=min(h,fr[k]);
                nr=max(nr,h*(k-j+1));
            }
            Right[i]=max(max(Right[i+1],Right[i]),nr);
            down[j]=max(max(down[j+1],down[j]),nr);
        }
    }
    int sol=0;
    for(i=1;i<n;++i) sol=max(sol,Left[i]+Right[i+1]);
    for(i=1;i<m;++i) sol=max(sol,up[i]+down[i+1]);
    g<<sol;
    return 0;
}