Cod sursa(job #2444329)

Utilizator robert.barbu27robert barbu robert.barbu27 Data 31 iulie 2019 10:56:24
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <iostream>

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

int n,m;
int  a[205][205],b[205][205],h[205],stiva[205],cnt,st[205],dr[205],dp[5][205];
void roteste()
{for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        b[j][n+1-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];
    }
}


}
void rezolva(int dir)
{
    for(int i=1;i<=m;i++)
    {
        h[i]=0;
    }
    for(int i=1;i<=n;i++)
    {dp[dir][i]=dp[dir][i-1];
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==0)
            {
                h[j]=h[j]+1;
            }
            else h[j]=0;
        }
        stiva[0]=0;
        cnt=0;
        for(int j=1;j<=m;j++)
        {
            while(cnt>0&&(h[stiva[cnt]]>=h[j]))
            {
                cnt--;
            }
            st[j]=stiva[cnt];
            stiva[++cnt]=j;
        }
        cnt=0;
        stiva[0]=m+1;
        for(int j=m;j>=1;j--)
        {
            while(cnt>0&&(h[stiva[cnt]]>=h[j]))
            {
                cnt--;
            }
            dr[j]=stiva[cnt];
            stiva[++cnt]=j;
        }
        for(int j=1;j<=m;j++)
        {
            if(dp[dir][i]<h[j]*(dr[j]-st[j]-1))
            {
                dp[dir][i]=h[j]*(dr[j]-st[j]-1);
            }
        }

    }
}
int main()
{

f>>n>>m;
char c;
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        f>>c;
        a[i][j]=int(c-48);
    }
}

for(int i=1;i<=4;i++)
{rezolva(i);
    roteste();

}

int sol=0;
for(int i=1;i<=n;i++)
{
    sol=max(sol,dp[1][i]+dp[3][n-i]);
}
for(int i=1;i<=m;i++)
{
    sol=max(sol,dp[2][i]+dp[4][m-i]);
}
g<<sol;
}