Cod sursa(job #3317741)

Utilizator radu_flradu fl radu_fl Data 25 octombrie 2025 10:36:41
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <iostream>
#include <fstream>
using namespace std;
const int MAX=205;
int a[MAX][MAX], b[MAX][MAX];
int h[MAX], sus[MAX],jos[MAX];
int m, n;
int aria_maxima(int n) {
    int i,j,minh,arie,maxa=0;
    for (i=1;i<=n;i++){
        minh=h[i];
        for (j=i;j>=1;j--) {
            if (h[j]==0) break;
            if (h[j]<minh) minh=h[j];
            arie=minh*(i-j+1);
            if (arie>maxa) maxa=arie;
        }
    }
    return maxa;
}
    int main() {
    ifstream fin("bmatrix.in");  
    ofstream fout("bmatrix.out");
    fin>>m>>n;
    char c;
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++) {
            fin>>c;
            a[i][j]=c-'0';
        }
    int i,j,aria,maxx,rasp1=0,rasp2=0;
    for (j=1;j<=n;j++) h[j]=0;
    maxx=0;
    for (i=1;i<=m;i++) {
        for (j=1;j<=n;j++) {
            if (a[i][j]==0) h[j]++;
            else h[j]=0;
        }
        aria=aria_maxima(n);
        if (aria>maxx) maxx=aria;
        sus[i]=maxx;
    }
    for (j=1;j<=n;j++) h[j]=0;
    maxx=0;
    for (i=m;i>=1;i--) {
        for (j=1;j<=n;j++) {
            if (a[i][j]==0) h[j]++;
            else h[j]=0;
        }
        aria=aria_maxima(n);
        if (aria>maxx) maxx=aria;
        jos[i]=maxx;
    }
    for (i=1;i<m;i++) {
        int s=sus[i]+jos[i+1];
        if (s>rasp1) rasp1=s; 
    }
    for (i=1;i<=m;i++)
        for (j=1;j<=n;j++)
            b[j][i]=a[i][j];
    int mm=n,nn=m;
    for (j=1;j<=nn;j++) h[j]=0;
    maxx=0;
    for (i=1;i<=mm;i++) {
        for (j=1;j<=nn;j++) {
            if (b[i][j]==0) h[j]++;
            else h[j]=0;
        }
        aria=aria_maxima(nn);
        if (aria>maxx) maxx=aria;
        sus[i]=maxx;
    }
    for (j=1;j<=nn;j++) h[j]=0;
    maxx=0;
    for (i=mm;i>=1;i--) {
        for (j=1;j<=nn;j++) {
            if (b[i][j]==0) h[j]++;
            else h[j]=0;
        }
        aria=aria_maxima(nn);
        if (aria>maxx) maxx=aria;
        jos[i]=maxx;
    }
    for (i=1;i<mm;i++) {
        int s=sus[i]+jos[i+1];
        if (s>rasp2) rasp2=s;
    }
    int rez;
    if (rasp1>rasp2) rez=rasp1;
    else rez=rasp2;
    fout<<rez<<"\n";
    fin.close();
    fout.close();
    return 0;
}