Cod sursa(job #1836131)

Utilizator SmitOanea Smit Andrei Smit Data 27 decembrie 2016 21:21:37
Problema BMatrix Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>
#define INF 2000000000

using namespace std;

int b[203][203],n,m,sol,stg[203],drp[203],t[203],st[203];
char a[203][203];

int Solutie(int xi, int yi, int xf, int yf)
{
    int i,j,L,rasp,top,x;
    rasp = -INF;
    L = yf - yi + 1;
    for(i = xi; i <= xf; ++i)
    {
        for(j = yi; j <= yf; ++j)
            t[j-yi+1] = max(0,b[i][j] - xi + 1);
        //stg
        t[0] = -INF - 1;
        top=0;
        st[top] = 0;
        for(j = 1; j <= L; ++j)
        {
            x = t[j];
            while(x <= t[st[top]])
                top--;
            stg[j] = j - st[top];
            st[++top]=j;
        }
        //drp
        t[L+1] = -INF - 1;
        top=0;
        st[top] = L+1;
        for(j = L; j >= 1; --j)
        {
            x = t[j];
            while(x <= t[st[top]])
                top--;
            drp[j] = st[top] - j;
            st[++top]=j;
        }
        for(j = 1; j <= L; ++j)
            if(t[j] != -INF)
                rasp = max(rasp,(stg[j] + drp[j] - 1) * t[j]);
    }
    return rasp;
}

int main()
{
    int i,j;
    ifstream fin("bmatrix.in");
    fin >> n >> m;
    for(i = 1; i <= n; ++i)
        fin >> (a[i]+1);
    fin.close();

    for(i = 1; i <= n; ++i)
        for(j = 1; j <= m; ++j)
            if(a[i][j] == '1')
                b[i][j] = -INF;
            else
                b[i][j] = max(0,b[i-1][j]) + 1;

    sol = -INF;
    for(i = 1; i < n; ++i)
        sol=max(sol,Solutie(1,1,i,m) + Solutie(i+1,1,n,m));
    for(j = 1; j < m; ++j)
        sol=max(sol,Solutie(1,1,n,j) + Solutie(1,j+1,n,m));

    ofstream fout("bmatrix.out");
    fout << sol << "\n";
    fout.close();
    return 0;
}