Cod sursa(job #1597996)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 12 februarie 2016 15:35:51
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include<iostream>
#include<fstream>
using namespace std;

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

const int N = 202;
int mat[N][N];
int n,m;
int v[N],h[N];
int sol;

int stiva[N], n_stiva;

int arie_histogram(int st, int dr)
{
    int j,top,arie,arie_max;

    stiva[0] = 0;
    n_stiva = 0;
    arie_max = 0;

    j = st;
    while(j <= dr)
    {
        top = stiva[n_stiva];
        if(n_stiva == 0 || h[top] <= h[j])
        {
            ++n_stiva;
            stiva[n_stiva] = j;
            ++j;
        }
        else
        {
            if(n_stiva == 1) arie = h[top] * (j - stiva[n_stiva - 1] - 1 - st + 1);
            else arie = h[top] * (j - stiva[n_stiva - 1] - 1);

            arie_max = max(arie, arie_max);

            --n_stiva;
        }
    }

    while(n_stiva > 0)
    {
        top = stiva[n_stiva];

        if(n_stiva == 1) arie = h[top] * (j - stiva[n_stiva - 1] - 1 - st + 1);
        else arie = h[top] * (j - stiva[n_stiva - 1] - 1);

        arie_max = max(arie, arie_max);

        --n_stiva;
    }

    return arie_max;
}

int solve()
{
    int i,j,mij,area1,area2,area1_max,area2_max,area_max;

    area_max = 0;

    for(i=1; i<=m; ++i) h[i] = 0;

    for(mij=2; mij<=m; ++mij)
    {
        area1_max = 0;
        area2_max = 0;
        for(i=1; i<=n; ++i)
        {
            for(j=1; j<=m; ++j)
            {
                if(mat[i][j] == 1) h[j] = 0;
                else ++h[j];
            }

            area1 = arie_histogram(1, mij-1);
            area2 = arie_histogram(mij, m);

            ///cout<<"i = "<<i<<", area1 = "<<area1<<", area2 = "<<area2<<"\n";

            area1_max = max(area1_max, area1);
            area2_max = max(area2_max, area2);
        }

        ///cout<<"mij = "<<mij<<", area1 = "<<area1_max<<", area2 = "<<area2_max<<"\n";
        area_max = max(area_max, area1_max + area2_max);
    }

    ///cout<<"AREA MAX = "<<area_max<<"\n";

    return area_max;
}

void flip_stanga()
{
    int newmat[N][N];
    int i,j;

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            newmat[m-j+1][i] = mat[i][j];
        }

    swap(n, m);
    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            mat[i][j] = newmat[i][j];
}

void afis()
{
    int i,j;

    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=m; ++j)
            cout<<mat[i][j];
        cout<<"\n";
    }
    cout<<"\n";
}

int main()
{
    int i,j;

    char sir[N];
    in>>n>>m;
    in.getline(sir, N);
    for(i=1; i<=n; ++i)
    {
        in.getline(sir, N);
        for(j=0; j<m; ++j) mat[i][j+1] = sir[j] - '0';
    }

    ///afis();
    sol = solve();
    ///cout<<"\n";

    flip_stanga();
    ///afis();
    sol = max(sol, solve());

    out<<sol;

    return 0;
}