Cod sursa(job #977069)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 24 iulie 2013 17:38:20
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.68 kb
#include <fstream>
#include <stack>

using namespace std;

/**
Line[i] = aria maxima a unui dreptunghi care se sprijina in jos pe linia i
Line2[i] = aria maxima a unui dreptunghi care se sprijina in sus pe linia i
PartialMax[i] = max(Line[1], Line[2]... Line[i])
PartialMax2[i] = max(Line2[i], Line2[i+1]... Line2[n])
sol = max(PartialMax[i] + PartialMax2[i+1] | i = 1..n-1);
apoi intorc matricea la 90 de grade si fac iar
*/

int n, m, sol;
char a[210][210];
int suma[210][210], suma2[210][210];
int Line[210], Line2[210], PartialMax[210], PartialMax2[210];
/**
    suma[i][j] = 0 daca a[i][j] = 1
    suma[i][j] = numarul de 0 consecutivi de deasupra elementului (i, j)

    suma2[i][j] = 0 daca a[i][j] = 1
    suma2[i][j] = numarul de 0 consecutivi de sub elementul (i, j)
*/

inline int max(int x, int y)
{
    return x>y?x:y;
}

inline void Read()
{
    ifstream f ("bmatrix.in");
    f>>n>>m;
    int i;
    for (i=1; i<=n; i++)
        f>>(a[i] + 1);
    f.close();
}

inline void Precalc()
{
    int i, j;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
        {
            if (a[i][j] == '0')
                suma[i][j] = suma[i-1][j] + 1;
            else
                suma[i][j] = 0;
        }
    for (i=n; i; i--)
        for (j=m; j; j--)
        {
            if (a[i][j] == '0')
                suma2[i][j] = suma2[i+1][j] + 1;
            else
                suma2[i][j] = 0;
        }
}

inline int Arie(int v[])
{
    int i;
    stack <int> st;
    int left[210], right[210], aux;
    /// avand histograma in vectorul v
    /// right[i] retine cea mai apropiata pozitie din dreapta lui i a.i. v[right[i]] < v[i]
    /// left[i] retine cea mai apropiata pozitie din stanga lui i a.i. v[left[i]] < v[i]


    for (i=1; i<=m; i++)
    {
        while (!st.empty() && v[i] < v[st.top()])
        {
            aux = st.top();
            st.pop();
            right[aux] = i;
        }
        st.push(i);
    }
    while (!st.empty())
    {
        aux = st.top();
        st.pop();
        right[aux] = m+1;
    }

    for (i=m; i; i--)
    {
        while (!st.empty() && v[i] < v[st.top()])
        {
            aux = st.top();
            st.pop();
            left[aux] = i;
        }
        st.push(i);
    }
    while (!st.empty())
    {
        aux = st.top();
        st.pop();
        left[aux] = 0;
    }

    int ret = 0;
    for (i=1; i<=m; i++)
        ret = max(ret, v[i] * (right[i] - left[i] - 1));
    return ret;
}

inline void Solve()
{
    Precalc();
    int i;
    for (i = 1; i <= n; i++)
    {
        Line[i] = Arie(suma[i]);
        Line2[i] = Arie(suma2[i]);
    }
    for (i=1; i<=n; i++)
        PartialMax[i] = max(PartialMax[i-1], Line[i]);
    for(i=n; i; i--)
        PartialMax2[i] = max(PartialMax2[i+1], Line2[i]);
    for (i=1; i<n; i++)
        sol = max(sol, PartialMax[i] + PartialMax2[i+1]);
}

inline void ReInit()
{
    int i, j;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            suma[i][j] = suma2[i][j] = 0;
    for (i=1; i<=n; i++)
        Line[i] = Line2[i] = PartialMax[i] = PartialMax2[i] = 0;
}

inline void Rotate90()
{
    int i, j;
    char aux[210][210];
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
        {
            aux[j][i] = a[i][j];
            a[i][j] = 0;
        }
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            a[i][j] = aux[i][j];
    swap(n, m);
}

inline void Write()
{
    ofstream g("bmatrix.out");
    g<<sol<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    ReInit();
    Rotate90();
    Solve();
    Write();
    return 0;
}