Cod sursa(job #876714)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 12 februarie 2013 00:42:19
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.19 kb
#include <iostream>
#include <fstream>

using namespace std;

int n, m, b[210][210], sol, b1[210][210];
char a[210][210];
struct stiva
{
    int x, poz;
};
stiva st[256];

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 int Amaxc(int x1, int y1, int x2, int y2)
{
    int vf;
    int i, j, val, maxim=0, poz, x;

    for (i=x1; i<=x2; i++)
    {
        val = 0;
        vf = 0;
        for (j=y1; j<=y2;  j++)
        {
            if (b[i][j])
            {
                x = b[i][j];
                if (st[vf].x > x)
                {
                    while (st[vf].x > x)
                    {
                        val = max (val, x * (j - st[vf].poz + 1));
                        vf--;
                    }
                    vf++;
                    st[vf].x = x;
                    st[vf].poz = j;
                }
                else
                    if (st[vf].x < x)
                    {
                        vf++;
                        st[vf].x = x;
                        st[vf].poz = j;
                    }
            }
            else
            {
                while (vf>0)
                {
                    val = max (val, st[vf].x * (j - st[vf].poz));
                    vf--;
                }
                vf = 0;
            }
        }
        while (vf>0)
        {
            val = max (val, st[vf].x * (y2 - st[vf].poz + 1));
            vf--;
        }
        maxim = max (maxim, val);
        val = 0;
        vf = 0;
        for (j=y2; j>=y1;  j--)
        {
            if (b[i][j])
            {
                x = b[i][j];
                if (st[vf].x > x)
                {
                    while (st[vf].x > x)
                    {
                        val = max (val, x * (st[vf].poz - j + 1));
                        vf--;
                    }
                    vf++;
                    st[vf].x = x;
                    st[vf].poz = j;
                }
                else
                    if (st[vf].x < x)
                    {
                        vf++;
                        st[vf].x = x;
                        st[vf].poz = j;
                    }
            }
            else
            {
                while (vf>0)
                {
                    val = max (val, st[vf].x * (st[vf].poz - j));
                    vf--;
                }
                vf = 0;
            }
        }
        while (vf>0)
        {
            val = max (val, st[vf].x * (st[vf].poz - y1 + 1)); //
            vf--;
        }
        maxim = max (maxim, val);
    }

    return maxim;
}

inline int Amaxl(int x1, int y1, int x2, int y2)
{
    int vf;
    int i, j, val, maxim=0, poz, x;

    for (j=y1; j<=y2; j++)
        if (b[x1-1][j])
        {
            for (i=x1; b[i][j] && i<=x2; i++)
                b1[i][j] = b[i][j] - b[x1-1][j];
            for (; i<=n; i++)
                b1[i][j] = b[i][j];
        }
        else
            for (i=x1; i<=x2; i++)
                b1[i][j] = b[i][j];

    for (i=x1; i<=x2; i++)
    {
        val = 0;
        vf = 0;
        for (j=y1; j<=y2;  j++)
        {
            if (b1[i][j])
            {
                x = b1[i][j];
                if (st[vf].x > x)
                {
                    while (st[vf].x > x)
                    {
                        val = max (val, x * (j - st[vf].poz + 1)); ////// st[vf].x
                        vf--;
                    }
                    vf++;
                    st[vf].x = x;
                    st[vf].poz = j;
                }
                else
                    if (st[vf].x < x)
                    {
                        vf++;
                        st[vf].x = x;
                        st[vf].poz = j;
                    }
            }
            else
            {
                while (vf>0)
                {
                    val = max (val, st[vf].x * (j - st[vf].poz));
                    vf--;
                }
                vf = 0;
            }
        }
        while (vf>0)
        {
            val = max (val, st[vf].x * (y2 - st[vf].poz + 1));
            vf--;
        }
        maxim = max (maxim, val);
        val = 0;
        vf = 0;
        for (j=y2; j>=y1;  j--)
        {
            if (b1[i][j])
            {
                x = b1[i][j];
                if (st[vf].x > x)
                {
                    while (st[vf].x > x)
                    {
                        val = max (val, x * (st[vf].poz - j + 1));
                        vf--;
                    }
                    vf++;
                    st[vf].x = x;
                    st[vf].poz = j;
                }
                else
                    if (st[vf].x < x)
                    {
                        vf++;
                        st[vf].x = x;
                        st[vf].poz = j;
                    }
            }
            else
            {
                while (vf>0)
                {
                    val = max (val, st[vf].x * (st[vf].poz - j));
                    vf--;
                }
                vf = 0;
            }
        }
        while (vf>0)
        {
            val = max (val, st[vf].x * (st[vf].poz - y1 + 1)); //
            vf--;
        }
        maxim = max (maxim, val);
    }
    return maxim;
}

inline void Solve()
{
    int i, j, val1, val2;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            if (a[i][j] == '0')
                b[i][j] = b[i-1][j] + 1;

    int linie, coloana;
    for (linie = 1; linie < n; linie++)
	{
		val1 = Amaxc(1, 1, linie, m);
		val2 = Amaxl(linie+1, 1, n, m);
		sol = max(sol, val1 + val2);

	}

    for (coloana = 1; coloana < m; coloana++)
	{
		val1 = Amaxc(1, 1, n, coloana);
		val2 = Amaxc(1, coloana+1, n, m);
		sol = max(sol, val1 + val2);
	}


}

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

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