Cod sursa(job #1737257)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 3 august 2016 16:31:29
Problema BMatrix Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <iostream>
#include <fstream>
#define NMAX 201
#include <stack>
using namespace std;

stack<int> stiva;

int a[NMAX][NMAX],v1[NMAX],v2[NMAX],n,m,a1,a2,arie;

int hisograma(int a[],int n)
{
    int arie = 0,amax = 0;
    stiva.push(0);
    for(int i=1;i<n;i++)
    {
        if(a[i]>=a[stiva.top()])
        {
            stiva.push(i);
        }
        else
        {
            while(!stiva.empty() && a[i]<a[stiva.top()])
            {
                arie =(i-stiva.top())*a[stiva.top()];
                amax = max(amax,arie);
                stiva.pop();
            }
            stiva.push(i);

        }

    }
    int last=0;
    while(!stiva.empty())
    {

        last = stiva.top();
        arie =(n-stiva.top())*a[stiva.top()];
        amax = max(amax,arie);
        stiva.pop();
    }

    amax = max(amax,a[last]*n);
    return amax;

}
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
char c;
int calc(int v[],int start, int finish)
{
    int arie=0;
    for(int i=0;i<m;i++)
        v[i] = 0;

    for(int i=start;i<finish;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]==1)
            {
                v[j]=0;
            }
            else
            {
                v[j]++;
            }
        }
//        for(int j=0;j<m;j++)
//        {
//            cout <<v[j] << " ";
//        }cout <<endl;
        //cout <<arie << " ";
        arie = max(arie,hisograma(v,m));
    }
    return arie;
}

int calc1(int v[],int start, int finish)
{
    int arie=0;
    for(int i=0;i<n;i++)
        v[i] = 0;

    for(int i=0;i<n;i++)
    {
        for(int j=start;j<finish;j++)
        {
            if(a[i][j]==1)
            {
                v[j]=0;
            }
            else
            {
                v[j]++;
            }
        }
//        for(int j=0;j<m;j++)
//        {
//            cout <<v[j] << " ";
//        }cout <<endl;
        //cout <<arie << " ";
        arie = max(arie,hisograma(v,m));
    }
    return arie;
}
int main()
{
    in >> n >> m;
    in.get();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            in.get(c);
            a[i][j] = c - '0';
        }
        in.get();
    }
   for(int i=1;i<n-1;i++)
   {
       a1 =calc(v1,0,i);
       a2 = calc(v1,i,n);
       arie = max(arie,a1+a2);
   }

     for(int i=1;i<m-1;i++)
   {
       a1 =calc1(v1,0,i);
       a2 = calc1(v1,i,n);
       arie = max(arie,a1+a2);
   }
    out <<arie;

    return 0;
}