Cod sursa(job #3315897)

Utilizator coldsh1tANdrei coldsh1t Data 16 octombrie 2025 15:30:39
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <iostream>
#include <fstream>

#define NMAX 1005

using namespace std;

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

char c[NMAX][NMAX];
long long a[NMAX], l[NMAX], r[NMAX], sus[NMAX], jos[NMAX], st[NMAX], dr[NMAX], s[NMAX];

int main()
{
    int n, m;
    long long ans=0;
    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            fin>>c[i][j];
        }
    }

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(c[i][j]=='0')
            {
                a[j]++;
            }
            else a[j]=0;
        }

        int k=0;
        s[0]=0;
        for(int j=1; j<=m; j++)
        {
            while(k>0 && a[j]<=a[s[k]])
                k--;
            l[j]=s[k];
            k++;
            s[k]=j;
        }

        k=0;
        s[0]=m+1;
        for(int j=m; j>=1; j--)
        {
            while(k>0 && a[j]<=a[s[k]])
                k--;
            r[j]=s[k];
            k++;
            s[k]=j;
        }

        for(int j=1; j<=m; j++)
        {
            st[j]=max(st[j-1], a[j]*(r[j]-l[j]-1));
            sus[i]=max(sus[i-1], a[j]*(r[j]-l[j]-1));
        }
    }

    for(int j=1; j<=m; j++) a[j]=0;

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

        int k=0;
        s[0]=0;
        for(int j=1; j<=m; j++)
        {
            while(k>0 && a[j]<=a[s[k]])
                k--;
            l[j]=s[k];
            k++;
            s[k]=j;
        }

        k=0;
        s[0]=m+1;
        for(int j=m; j>=1; j--)
        {
            while(k>0 && a[j]<=a[s[k]])
                k--;
            r[j]=s[k];
            k++;
            s[k]=j;
        }

        for(int j=m; j>=1; j--)
        {
            dr[j]=max(dr[j+1], a[j]*(r[j]-l[j]-1));
            jos[i]=max(jos[i+1], a[j]*(r[j]-l[j]-1));
        }
    }

    for(int j=1; j<m; j++)
    {
        ans=max(ans, st[j]+dr[j+1]);
    }
    for (int i=1; i<n; i++)
    {
        ans=max(ans, sus[i]+jos[i + 1]);
    }
    fout<<ans;
    return 0;
}