Cod sursa(job #926914)

Utilizator ericptsStavarache Petru Eric ericpts Data 25 martie 2013 14:06:19
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define maxn 220
char norm[maxn][maxn];
char flip[maxn][maxn];
int n,m,lv,st[maxn],bagat[maxn],sus[maxn],jos[maxn];
int up[maxn][maxn],down[maxn][maxn];
int left[maxn],right[maxn];
int best_up[maxn],best_down[maxn];
void reset()
{
    memset(st,0,sizeof(st));
    memset(bagat,0,sizeof(bagat));
    memset(left,0,sizeof(left));
    memset(right,0,sizeof(right));
    lv=0;
}

void form(int h[maxn][maxn],int n,int m,int i)
{
    int j;
    reset();
    for(j=1;j<=m;++j){

        while(lv > 0 && st[lv] >= h[i][j]){
            right[bagat[lv]] = j-1;//am gasit capatul din dreapta pt. dreptunghiul de inaltime st[lv]
                                  //din varful stivei
                                 //intrucat inaltimea curenta < cea necesara pt. continuarea lui
            --lv;
        }
        left[j] = bagat[lv] + 1;
        ++lv;
        st[lv] = h[i][j];
        bagat[lv] = j;

        }
        while(lv>0)
            right[bagat[lv--]]=m;    //capetele nescoase se pot extinda pana la capatul matricii
}


int solve(char mat[maxn][maxn],int n,int m)
{

    int i,j,ret=0;
    memset(best_up,0,sizeof(best_up));
    memset(best_down,0,sizeof(best_down));
    memset(&up[0][0],0,sizeof(up));
    memset(&down[0][0],0,sizeof(down));

    for(i=1;i<=n;++i)//up[i][j] = numarul de 0-uri consecutive deasupra punctului (i,j)
        for(j=1;j<=m;++j){
            if(mat[i][j] == '0')
                up[i][j] = up[i-1][j] + 1;
            else
                up[i][j] = 0;
        }
    for(i=n;i>0;--i)//down[i][j] = same shit doar ca dedesuptul lui
        for(j=1;j<=m;++j){
            if(mat[i][j] == '0')
                down[i][j] = down[i+1][j] + 1;
            else
                down[i][j] = 0;
    }for(i=1;i<=n;++i){
        form(up,n,m,i);

        best_up[i] = best_up[i-1];
        for(j=1;j<=m;++j){//calculez aria dreptunghiurilor folosindu-ma de cele 2 capete
            best_up[i] = max(best_up[i] , up[i][j] * (right[j] - left[j] + 1 ) );
            best_up[i] = max(best_up[i] , up[i][j]);
        }



        form(down,n,m,i);

        best_down[i]=0;
        for(j=1;j<=m;++j){
            best_down[i] = max(best_down[i] , down[i][j] * (right[j] - left[j] + 1 ) );
            best_down[i] = max(best_down[i] , down[i][j]);
        }
    }for(i=1;i<n;++i){
        ret = max(ret,best_up[i] + best_down[i+1]);
    }

    return ret;
}

int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);

    int i,j;
    scanf("%d %d\n",&n,&m);
    for(i=1;i<=n;++i){
        scanf("%s\n",norm[i]+1);
        for(j=1;j<=m;++j)
            flip[j][i] = norm[i][j];
    }
    printf("%d\n", max(solve(norm,n,m)//cazul cand cele 2 dreptunghiuri sunt despartite de o linie orizontala
              ,solve(flip,m,n)));//si cazul cand sunt despartite de o linie verticala
    fflush(stdout);
}