Cod sursa(job #2799469)

Utilizator VladMxPMihaila Vlad VladMxP Data 13 noiembrie 2021 11:29:35
Problema BMatrix Scor 28
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
char s[205][205];
int n,m,d[205],st[205],dr[205],sus[205],jos[205];

int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        fin>>s[i]+1;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='0')
                d[j]++; // cate 0-uri se afla pe colana j intre liniile 1-i
            else d[j]=0;

            int nr=0,h=2e9;
            for(int k=j;k>=1&&h>0;k--)
            {
                h=min(h,d[k]);
                nr=max(nr,h*(j-k+1)); // nr = aria maxima a unui dreptunghi cu coltul dreapta jos i,j
            }

            sus[i]=max(max(sus[i-1],sus[i]),nr); // deasupra liniei i se obtine dreptunghi de arie maxima sus[i]
            st[j]=max(max(st[j-1],st[j]),nr); // la stanga coloanei j se obtine dreptunghi de arie maxima st[i]
        }
    }

    memset(d,0,sizeof(d));
    for(int i=1;i<=200;i++)
        cout<<d[i];

    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            if(s[i][j]=='0')
                d[j]++; // cate 0-uri se afla pe coloana j intre liniile i-n
            else d[j]=0;

            int nr=0,h=2e9;
            for(int k=j;k<=m&&h>0;k++)
            {
                h=min(h,d[k]);
                nr=max(nr,h*(k-j+1)); // nr = aria maxima a unui dreptunghi cu coltul stanga sus i,j
            }

            jos[i]=max(max(jos[i-1],jos[i]),nr); // sub linia i se obtine dreptunghi de arie maxima jos[i]
            dr[j]=max(max(dr[j-1],dr[j]),nr); // la dreapta coloanei j se obtine dreptunghi de arie maxima dr[i]
        }
    }

    int sol=0;
    for(int i=1;i<n;i++)sol=max(sol,sus[i]+jos[i+1]);
    for(int j=1;j<m;j++)sol=max(sol,st[j]+dr[j+1]);

    fout<<sol;
}