Cod sursa(job #1592617)

Utilizator akaprosAna Kapros akapros Data 7 februarie 2016 19:59:54
Problema BMatrix Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <bits/stdc++.h>
#define maxN 202
using namespace std;
int n, m, s[maxN][maxN], rs[maxN][maxN], dp, top, sol, maxA[maxN];
char a[maxN][maxN], cp[maxN][maxN];
struct st
{
    int h, p;
} st[maxN];
void read()
{
    int i;
    freopen("bmatrix.in", "r", stdin);
    scanf("%d %d\n", &n, &m);
    for (i = 1; i <= n; ++ i)
        gets(a[i] + 1);
}
void partial_sums()
{
    int i, j;
    for (i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
            if (a[i][j] == '0')
                s[i][j] = s[i - 1][j] + 1;

    for (i = n; i >= 1; -- i)
        for (j = 1; j <= m; ++ j)
            if (a[i][j] == '0')
                rs[i][j] = rs[i + 1][j] + 1;
}
void get_maxA()
{
    int i, j, p, A;
    for (i = n; i >= 1; -- i)
    {
        maxA[i] = 0;
        top = 0;
        for (j = 1; j <= m + 1; ++ j)
        {
            p = j;
            if (rs[i][j] > st[top].h)
            {
                st[++ top].p = j;
                st[top].h = rs[i][j];
            }
            else
            {
                while (st[top].h > rs[i][j])
                {
                    A = st[top].h * (j - st[top].p);
                    if (A > maxA[i])
                        maxA[i] = A;
                    -- top;
                }
                if (rs[i][j] > 0)
                {
                    st[++ top].h = rs[i][j];
                    st[top].p = p;
                }
            }
        }
    }
}
void get_sol()
{
    int i, j, a, p, A;
    top = 0;
    for (i = 1; i <= n; ++ i)
    {
        a = 0;
        for (j = 1; j <= m + 1; ++ j)
        {
            p = j;
            if (s[i][j] > st[top].h)
            {
                st[++ top].p = j;
                st[top].h = s[i][j];
            }
            else
            {
                while (st[top].h > s[i][j])
                {
                    A = st[top].h * (j - st[top].p);
                    if (A > a)
                        a = A;
                    -- top;
                }
                if (s[i][j] > 0)
                {
                    st[++ top].h = s[i][j];
                    st[top].p = p;
                }
            }
        }

        if (a + maxA[i + 1] > sol)
            sol = a + maxA[i + 1];

    }
}
void solve()
{
    partial_sums();
    get_maxA();
    get_sol();
}
void rotate_mat()
{
    int i, j;
    memcpy(cp, a, sizeof(a));
    swap(n, m);
    for (i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
            a[i][j] = cp[n - j + 1][i];
}
void write()
{
    freopen("bmatrix.out", "w", stdout);
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    rotate_mat();
    memset(s, 0, sizeof(s));
    memset(rs, 0, sizeof(rs));
    memset(maxA, 0, sizeof(maxA));
    solve();
    write();
    return 0;
}