Cod sursa(job #1836204)

Utilizator SmitOanea Smit Andrei Smit Data 27 decembrie 2016 22:48:40
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 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,N,M;
    N = xf - xi + 1;
    M = yf - yi + 1;
    for(i = xi; i <= xf; ++i)
        for(j = yi; j <= yf; ++j)
            if(a[i][j] == '1')
                b[i-xi+1][j-yi+1] = 0;
            else
                b[i-xi+1][j-yi+1] = b[i-xi][j] + 1;
    rasp = -INF;
    L = yf - yi + 1;
    for(i = 1; i <= N; ++i)
    {
        for(j = 1; j <= M; ++j)
            t[j] = b[i][j];
        //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();
    Solutie(10,1,n,m);

    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;
}