Cod sursa(job #3318166)

Utilizator radu_flradu fl radu_fl Data 27 octombrie 2025 13:01:40
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX=2005;
int n,m,a[NMAX][NMAX];
long long h[NMAX];
int st[NMAX],dr[NMAX],s[NMAX];
long long skyline(long long h[], int m) {
    int st[NMAX], dr[NMAX], s[NMAX];
    long long sump[NMAX];
    sump[0]=0;
    for (int i=1;i<=m;i++)
        sump[i]=sump[i-1]+1; 
    int sp=0;
    for (int i=1;i<=m;i++) {
        while (sp>0 && h[s[sp]]>=h[i])
            sp--;
        if (sp==0)
            st[i]=0;
        else
            st[i]=s[sp];
        s[++sp]=i;
    }
    sp=0;
    for (int i=m;i>=1;i--) {
        while (sp>0 && h[s[sp]]>=h[i])
            sp--;
        if (sp==0)
            dr[i]=m+1;
        else
            dr[i]=s[sp];
        s[++sp]=i;
    }
    long long rasp=0;
    for (int i=1;i<=m;i++) {
        long long lung=sump[dr[i]-1]-sump[st[i]];
        long long aria=h[i]*lung;
        if (aria>rasp)
            rasp=aria;
    }
    return rasp;
}

int main(){
    ifstream fin("bmatrix.in");
    ofstream fout("bmatrix.out");
    fin>>n>>m;
    for(int i=1;i<=n;i++){
        string x;
            fin>>x;
        for(int j=1;j<=m;j++)
            a[i][j]=x[j-1]-'0';
    }

    long long sus[NMAX],jos[NMAX],rasp=0,amax;
    for(int j=1;j<=m;j++)
        h[j]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0) 
                h[j]=h[j]+1;
            else 
                h[j]=0;
        }
        amax=skyline(h,m);
        if(i==1) 
            sus[i]=amax;
        else 
            sus[i]=max(sus[i-1],amax);
    }
    for(int j=1;j<=m;j++)h[j]=0;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0) 
                h[j]=h[j]+1;
            else 
                h[j]=0;
        }
        amax=skyline(h,m);
        if(i==n) 
            jos[i]=amax;
        else 
            jos[i]=max(jos[i+1],amax);
    }
    for(int i=1;i<n;i++) 
        rasp=max(rasp,sus[i]+jos[i+1]);
    int b[NMAX][NMAX];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            b[j][i]=a[i][j];
    swap(n,m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            a[i][j]=b[i][j];
    for(int j=1;j<=m;j++) 
        h[j]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0) 
                h[j]=h[j]+1;
            else 
                h[j]=0;
        }
        amax=skyline(h,m);
        if(i==1) 
            sus[i]=amax;
        else 
            sus[i]=max(sus[i-1],amax);
    }
    for(int j=1;j<=m;j++) 
        h[j]=0;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0) 
                h[j]=h[j]+1;
            else 
                h[j]=0;
        }
        amax=skyline(h,m);
        if(i==n) 
            jos[i]=amax;
        else 
            jos[i]=max(jos[i+1],amax);
    }

    for(int i=1;i<n;i++) 
        rasp=max(rasp,sus[i]+jos[i+1]);

    fout<<rasp<<"\n";
    return 0;
}