Cod sursa(job #2027004)

Utilizator KonoplyankaKonoplyanka Konoplyanka Data 25 septembrie 2017 14:31:34
Problema BMatrix Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 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,k=ult=0;j<=m;++j)
    {
        if(M[i][j]=='0')
        {
            ++fr[j];
            int nr=0;
            while(k&&fr[D[k]]>=fr[j])
            {
                nr=max(nr,fr[j]*(j-D[k]+1));
                --k;
            }
            if(!k) nr=max(nr,fr[j]*(j-ult));
            else nr=max(nr,fr[D[1]]*(j-D[1]+1));
            up[i]=max(up[i],max(up[i-1],nr));
            Left[j]=max(Left[j],max(Left[j-1],nr));
            D[++k]=j;
            continue;
        }
        fr[j]=k=0;
        ult=j;
    }
    for(i=1;i<=m;++i) fr[i]=0;
    for(i=n;i>0;--i)
        for(j=m,k=0,ult=m+1;j>0;--j)
    {
        if(M[i][j]=='0')
        {
            ++fr[j];
            int nr=0;
            while(k&&fr[D[k]]>=fr[j])
            {
                nr=max(nr,fr[j]*(D[k]-j+1));
                --k;
            }
            if(!k) nr=max(nr,fr[j]*(ult-j));
            else nr=max(nr,fr[D[1]]*(D[1]-j+1));
            down[i]=max(down[i],max(down[i+1],nr));
            Right[j]=max(Right[j],max(Right[j+1],nr));
            D[++k]=j;
            continue;
        }
        fr[j]=k=0;
        ult=j;
    }
    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;
}