Cod sursa(job #874561)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 8 februarie 2013 20:08:35
Problema BMatrix Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.65 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;

    for (i=x1; i<=x2; i++)
    {
        val = 0;
        vf = 0;
        for (j=y1; j<=y2; j++)
        {
            if (b[i][j])
            {

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

    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])
            {

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

inline void Solve()
{
    int i, j;
    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++)
        sol = max(sol, Amaxc(1, 1, linie, m) + Amaxl(linie+1, 1, n, m));


    for (coloana = 1; coloana <= m; coloana++)
        sol = max(sol, Amaxc(1, 1, n, coloana) + Amaxc(1, coloana+1, n, m));

}

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

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