Cod sursa(job #1825401)

Utilizator DobosDobos Paul Dobos Data 9 decembrie 2016 08:42:58
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <bits/stdc++.h>
#define NMAX 210

#define INF 1e9

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

int Sa[NMAX][NMAX],Sb[NMAX][NMAX];

int Mmaxa(int n,int m,int M){
    int A = 0;
    for(int i = n; i <= m; i++){
        int la = 0,ha = INF;
        for(int j = 1; j <= M; j++){
            if(Sa[i][j]){
                la++;
                if(Sa[i][j] > i - n + 1)
                    ha = min(ha,Sa[i][j] - Sa[n - 1][j]);
                else
                    ha = min(ha,Sa[i][j]);
                A = max(A,ha * la);
            } else{
                la = 0;
                ha = INF;
            }

        }
    }

    return A;

}

int Mmaxb(int n,int m,int M){
    int A = 0;
    for(int j = n; j <= m; j++){
        int lb = 0,hb = INF;
        for(int i = 1; i <= M; i++){
            if(Sb[i][j]){
                lb++;
                if(Sb[i][j] > i - n + 1)
                    hb = min(hb,Sb[i][j] - Sb[i][n - 1]);
                else
                    hb = min(hb,Sb[i][j]);
                A = max(A,hb * lb);
            } else{
                lb = 0;
                hb = INF;
            }

        }
    }

    return A;

}




int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int n,m,sol;
    char x;

    fin >> n >> m;

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= m; j++){

            fin >> x;

            if(x == '0'){
                Sa[i][j] = Sa[i - 1][j] + 1;
                Sb[i][j] = Sb[i][j - 1] + 1;
            }
        }
    }

    sol = 0;

    for(int k = 1; k < n; k++){

        sol = max(sol,Mmaxa(1,k,m) + Mmaxa(k + 1,n,m));

    }
    for(int k = 1; k < m; k++){

        sol = max(sol,Mmaxb(1,k,n) + Mmaxb(k + 1,m,n));

    }
        fout << sol ;

    return 0;
}