Cod sursa(job #2696060)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 15 ianuarie 2021 10:28:59
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 kb
#include<cstdio>
#include<stack>
#include<algorithm>
using namespace std;
FILE*in=fopen("bmatrix.in","r");
FILE*out=fopen("bmatrix.out","w");
struct stac
{
    int val,nr;
};
stac stc;
stack<stac> stec;
int n,m,i,j,v[201],vs[201],os[201],vj[201],od[201],st[201],dr[201],a[4][201],area,maxarea,rarea,dare;
char c;
bool mat[201][201];
void rot()
{
    int rotm[201][201];
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            rotm[j][m+1-i]=mat[i][j];
        }
    }
    swap(m,n);
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            mat[i][j]=rotm[i][j];
        }
    }
}
void f(int x)
{
    for(i=1;i<=n;i++)
    {
        v[i]=0;
    }
    for(i=1;i<=m;i++)
    {
        dr[1]=1;
        st[n]=n;
        for(j=1;j<=n;j++)
        {
            if(mat[i][j]==0)
            {
                v[j]++;
            }
            else
            {
                v[j]=0;
            }
            while(!stec.empty())
            {
                stc=stec.top();
                if(stc.val<=v[j])
                {
                    break;
                }
                else
                {
                    dr[stc.nr]=j-1;
                    stec.pop();
                }
            }
            stc.val=v[j];
            stc.nr=j;
            stec.push(stc);
        }
        while(!stec.empty())
        {
            stc=stec.top();
            dr[stc.nr]=n;
            stec.pop();
        }
        for(j=n;j>=1;j--)
        {
            while(!stec.empty())
            {
                stc=stec.top();
                if(stc.val<=v[j])
                {
                    break;
                }
                else
                {
                    st[stc.nr]=j+1;
                    stec.pop();
                }
            }
            stc.val=v[j];
            stc.nr=j;
            stec.push(stc);
        }
        while(!stec.empty())
        {
            stc=stec.top();
            st[stc.nr]=1;
            stec.pop();
        }
        maxarea=0;
        for(j=1;j<=n;j++)
        {
            area=(dr[j]-st[j]+1)*v[j];
            if(maxarea<area)
            {
                maxarea=area;
            }
        }
        a[x][i]=maxarea;
    }
}
int main()
{
    fscanf(in,"%d%d",&m,&n);
    fgetc(in);
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            c=fgetc(in);
            mat[i][j]=c-48;
        }
        fgetc(in);
    }
    f(0);
    rot();
    f(1);
    rot();
    f(2);
    rot();
    f(3);
    rot();
    for(i=1;i<=m-1;i++)
    {
        for(j=i+1;j<=m;j++)
        {
            dare=a[0][i]+a[2][m+1-j];
            if(rarea<dare)
            {
                rarea=dare;
            }
        }
    }
    for(i=1;i<=n-1;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            dare=a[1][i]+a[3][n+1-j];
            if(rarea<dare)
            {
                rarea=dare;
            }
        }
    }
    fprintf(out,"%d",rarea);
}