Cod sursa(job #2231055)

Utilizator armigheGheorghe Liviu Armand armighe Data 12 august 2018 20:04:17
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
char a[202][202];
int h[202][202],st[202];
int amax(int l1,int c1,int l2,int c2)
{
    int i,j,v,arie,maxim=0;
    for(j=c1;j<=c2;j++)
    {
        v=0;
        st[0]=l1-1;
        for(i=l1;i<=l2;i++)
        {
            while(v>0&&min(h[i][j],j-c1+1)<=min(h[st[v]][j],j-c1+1))
            {
                arie=min(h[st[v]][j],j-c1+1)*(st[v]-st[v-1]);
                if(arie>maxim)
                    maxim=arie;
                v--;
            }
            st[++v]=i;
        }
        while(v>0)
        {
            arie=min(h[st[v]][j],j-c1+1)*(st[v]-st[v-1]);
            if(arie>maxim)
                maxim=arie;
            v--;
        }
    }
    return maxim;
}

int main()
{
    int m,n,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;
    }
    for(i=1;i<=m-1;i++)
    {
        x=amax(1,1,i,n);
        x+=amax(i+1,1,m,n);
        if(x>sol)
            sol=x;
    }
    for(j=1;j<=n-1;j++)
    {
        x=amax(1,1,m,j)+amax(1,j+1,m,n);
        if(x>sol)
            sol=x;
    }
    g<<sol;
    return 0;
}