Cod sursa(job #3178362)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 1 decembrie 2023 17:08:24
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <cstring>
#include <bitset>
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
int n,m,i,j,nr1,nr2,maxim,st[201],dr[201],l[201],stiva[201];
bitset <201> v[201];
char ch;
int f (int a,int b,int n,int m)
{
    memset (l,0,sizeof (l));
    memset (st,0,sizeof (st));
    memset (dr,0,sizeof (dr));
    memset (stiva,0,sizeof (stiva));
    int i,j,k,aria,maxc=0;
    for (i=a; i<=n; i++)
    {
        for (j=b; j<=m; j++)
        {
            if (v[i][j]==0)
                l[j]++;
            else
                l[j]=0;
        }
        k=0;
        for (j=b; j<=m; j++)
        {
            while (k>0&&l[j]<=l[stiva[k]])
                k--;
            if (k>0)
                st[j]=stiva[k]+1;
            else
                st[j]=b;
            k++;
            stiva[k]=j;
        }
        k=0;
        for (j=m; j>=b; j--)
        {
            while (k>0&&l[j]<=l[stiva[k]])
                k--;
            if (k>0)
                dr[j]=stiva[k]-1;
            else
                dr[j]=m;
            k++;
            stiva[k]=j;
        }
        for (j=b; j<=m; j++)
        {
            aria=(dr[j]-st[j]+1)*l[j];
            if (aria>maxc)
                maxc=aria;
        }
    }
    return maxc;
}
int main()
{
    fin>>n>>m;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            fin>>ch;
            v[i][j]=ch-'0';
        }
    }
    for (i=1; i<n; i++)
    {
        nr1=f (1,1,i,m);
        nr2=f (i+1,1,n,m);
        if (nr1+nr2>maxim)
            maxim=nr1+nr2;
    }
    for (j=1; j<m; j++)
    {
        nr1=f (1,1,n,j);
        nr2=f (1,j+1,n,m);
        if (nr1+nr2>maxim)
            maxim=nr1+nr2;
    }
    fout<<maxim;
    return 0;
}