Cod sursa(job #2255056)

Utilizator borbonzolaBono Borbonzola borbonzola Data 6 octombrie 2018 13:04:45
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <fstream>
#include <stack>

using namespace std;

ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");

void Read ();
void Solve ();
int GetMaxArea (int [], int);
void DisplayAnswer ();

int N, M, m[1005][1005], f[1005][1005], answer;

int main()
{
    Read();
    Solve();
    DisplayAnswer();
}

void Read ()
{
    fin >> N >> M;
    for (int i=1; i<=N; ++i)
    {
        char c[1005];
        fin >> c;
        for (int j=0; j<M; ++j)
            m[i][j+1]=c[j]-'0';
    }
}

void Solve ()
{
    for (int i=1; i<=N; ++i)
        for (int j=1; j<=M; ++j)
        {
            if (m[i][j]==0)
                f[i][j]=1+f[i-1][j];
            else
                f[i][j]=0;
        }

    int H[1005]={0};

    for (int i=1; i<=N; ++i)
    {
        for (int j=1; j<=M; ++j)
            H[j]=f[i][j];
        answer=max(answer, GetMaxArea(H, M+1));
    }
}

int GetMaxArea (int hist[], int n)
{
    // Create an empty stack. The stack holds indexes
    // of hist[] array. The bars stored in stack are
    // always in increasing order of their heights.
    stack<int> s;

    int max_area = 0; // Initalize max area
    int tp;  // To store top of stack
    int area_with_top; // To store area with top bar
                       // as the smallest bar

    // Run through all bars of given histogram
    int i = 1;
    while (i < n)
    {
        // If this bar is higher than the bar on top
        // stack, push it to stack
        if (s.empty() || hist[s.top()] <= hist[i])
            s.push(i++);

        // If this bar is lower than top of stack,
        // then calculate area of rectangle with stack
        // top as the smallest (or minimum height) bar.
        // 'i' is 'right index' for the top and element
        // before top in stack is 'left index'
        else
        {
            tp = s.top();  // store the top index
            s.pop();  // pop the top

            // Calculate the area with hist[tp] stack
            // as smallest bar
            area_with_top = hist[tp] * (s.empty() ? i :
                                   i - s.top() - 1);

            // update max area, if needed
            if (max_area < area_with_top)
                max_area = area_with_top;
        }
    }

    // Now pop the remaining bars from stack and calculate
    // area with every popped bar as the smallest bar
    while (s.empty() == false)
    {
        tp = s.top();
        s.pop();
        area_with_top = hist[tp] * (s.empty() ? i :
                                i - s.top() - 1);

        if (max_area < area_with_top)
            max_area = area_with_top;
    }

    return max_area;
}

void DisplayAnswer ()
{
    fout << answer;
}