Cod sursa(job #3179302)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 3 decembrie 2023 14:39:29
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

#define DIM 200

using namespace std;

//ifstream f("in.in");
//ofstream g("out.out");

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

int n,m;
int a[DIM+5][DIM+5],v[DIM+5];
char chr;

int sol = 0,solTmp;
stack <int> q;

int solve(int x1,int y1,int x2,int y2){

    solTmp = 0;
    for(int i=1;i<=m;i++){
        v[i] = 0;
    }

    for(int i=x1;i<=x2;i++){

        while(!q.empty()){
            q.pop();
        }

        for(int j=y1;j<=y2+1;j++){
            if(a[i][j]){
                v[j] = 0;
            }else{
                v[j]++;
            }

            if(j == y2+1){ ///opritor ca sa se calculeze ce ramane
                v[j] = 0;
            }

            while(!q.empty() && v[j] <= v[q.top()]){

                int h = v[q.top()];
                q.pop();
                int l = j-1;

                if(!q.empty()){
                    l-=q.top();
                }else{
                    l-=(y1-1);
                }

                solTmp = max(solTmp,l*h);

            }


            q.push(j);

        }
    }

    return solTmp;

}


signed main(){

    f>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f>>chr;
            a[i][j] = chr-'0';
        }
    }

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

        int s1 = solve(1,1,i,m);
        int s2 = solve(i+1,1,n,m);

        sol = max(sol,s1+s2);
    }

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

        int s1 = solve(1,1,n,i);
        int s2 = solve(1,i+1,n,m);

        sol = max(sol,s1+s2);
    }

    g<<sol;


    return 0;
}