Cod sursa(job #3318162)

Utilizator radu_flradu fl radu_fl Data 27 octombrie 2025 12:56:43
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.84 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){
    long long r=0;
    int st1[NMAX],dr1[NMAX],s1[NMAX],sp;
    sp=0;
    for(int j=1;j<=m;j++){
        while(sp>0&&h[s1[sp]]>=h[j])
        sp--;
        if(sp==0)
            st1[j]=0;
        else 
            st1[j]=s1[sp];
        s1[++sp]=j;
    }
    sp=0;
    for(int j=m;j>=1;j--){
        while(sp>0&&h[s1[sp]]>=h[j])
            sp--;
        if(sp==0)
            dr1[j]=m+1;
        else 
            dr1[j]=s1[sp];
        s1[++sp]=j;
    }
    for(int j=1;j<=m;j++){
        long long l=dr1[j]-st1[j]-1;
        long long aria=h[j]*l;
        if(aria>r)r=aria;
    }
    return r;
}

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;
}