Cod sursa(job #2242280)

Utilizator armigheGheorghe Liviu Armand armighe Data 18 septembrie 2018 11:11:50
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
char a[202][202],b[202][202];
int m,n,h[202][202],st[202],dmax[4][202],d;
void amax()
{
    int i,j,v,arie;
    for(j=1;j<=n;j++)
    {
        v=0;
        for(i=1;i<=m;i++)
        {
            while(v>0&&h[i][j]<=h[st[v]][j])
            {
                arie=h[st[v]][j]*(i-1-st[v-1]);
                dmax[d][i-1]=max(dmax[d][i-1],arie);
                dmax[d][st[v]]=max(dmax[d][st[v]],h[st[v]][j]*(st[v]-st[v-1]));
                v--;
            }
            st[++v]=i;
        }
        while(v>0)
        {
            arie=h[st[v]][j]*(m-st[v-1]);
            dmax[d][m]=max(dmax[d][m],arie);
            dmax[d][st[v]]=max(dmax[d][st[v]],h[st[v]][j]*(st[v]-st[v-1]));
            v--;
        }
    }
    for(i=2;i<=m;i++)
        dmax[d][i]=max(dmax[d][i],dmax[d][i-1]);
}

void rotire()
{
    int i,j;
    for(i=0;i<=201;i++)
    for(j=0;j<=201;j++)
        h[i][j]=0;
    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
        b[j][m-i+1]=a[i][j];
    swap(m,n);
    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
        a[i][j]=b[i][j];
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        if(a[i][j]=='0')
            h[i][j]=h[i][j-1]+1;
    }
}

int main()
{
    int i,j,sol=0,x;
    f>>m>>n;
    f.get();
    for(i=1;i<=m;i++)
        f.getline(a[i]+1,201);
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        if(a[i][j]=='0')
            h[i][j]=h[i][j-1]+1;
    }
    d=0;
    amax();
    rotire();
    d=1;
    amax();
    rotire();
    d=2;
    amax();
    rotire();
    d=3;
    amax();
    rotire();
    for(i=0;i<m;i++)
    {
        x=dmax[0][i]+dmax[2][m-i];
        if(x>sol)
            sol=x;
    }
    for(i=0;i<n;i++)
    {
        x=dmax[1][i]+dmax[3][n-i];
        if(x>sol)
            sol=x;
    }
    g<<sol;
    return 0;
}