Cod sursa(job #3178411)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 1 decembrie 2023 17:41:49
Problema BMatrix Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 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];
int poz1[201],poz2[201];
bool v[201][201],aux[201][201];
char ch;
void f (int a,int val,int sol[])
{
    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;
    for (i=a; i<=n&&i>0; i+=val)
    {
        for (j=1; j<=m; j++)
        {
            if (v[i][j]==0)
                l[j]++;
            else
                l[j]=0;
        }
        k=0;
        for (j=1; j<=m; j++)
        {
            while (k>0&&l[j]<=l[stiva[k]])
                k--;
            if (k>0)
                st[j]=stiva[k]+1;
            else
                st[j]=1;
            k++;
            stiva[k]=j;
        }
        k=0;
        for (j=m; j>0; 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=1; j<=m; j++)
        {
            aria=(dr[j]-st[j]+1)*l[j];
            if (aria>sol[i])
                sol[i]=aria;
        }
    }
}
int main()
{
    fin>>n>>m;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            fin>>ch;
            v[i][j]=ch-'0';
        }
    }
    f (1,1,poz1);
    f (n,-1,poz2);
    for (i=1; i<n; i++)
    {
        if (poz1[i]+poz2[i+1]>maxim)
            maxim=poz1[i]+poz2[i+1];
    }
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
            aux[j][i]=v[i][j];
    }
    swap (n,m);
    memset (v,0,sizeof (v));
    memcpy (v,aux,sizeof (aux));
    memset (poz1,0,sizeof (poz1));
    memset (poz2,0,sizeof (poz2));
    f (1,1,poz1);
    f (n,-1,poz2);
    for (i=1; i<n; i++)
    {
        if (poz1[i]+poz2[i+1]>maxim)
            maxim=poz1[i]+poz2[i];
    }
    fout<<maxim;
    return 0;
}