Cod sursa(job #2919062)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 15 august 2022 00:42:53
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>
#define nmax 205
#define rf(i,a) for(int i=a-1;i>=0;i--)
#define fr(i,a) for(int i=0;i<a;i++)
using namespace std;

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

bool mt[nmax][nmax];
int n,m;

int st[nmax],dr[nmax];
int stk[nmax],k;
int col[nmax];
int beach(const int &l)
{
    k=0;
    fr(i,l)
    {
        while(k>0&&col[stk[k-1]]>=col[i]) k--;

        st[i]=k==0?-1:stk[k-1];

        stk[k++]=i;
    }
    k=0;
    rf(i,l)
    {
        while(k>0&&col[stk[k-1]]>=col[i]) k--;

        dr[i]=k==0?l:stk[k-1];

        stk[k++]=i;
    }
    int mx=0;
    fr(i,l)
    {
        mx=max(mx,col[i]*(dr[i]-st[i]-1));
    }
    return mx;
}

void solveside(int *v, int side)
{
    int a,b,c;
    switch(side)
    {
    case 0:
        a=0; b=n;
        c=m;
        break;
    case 1:
        a=n-1; b=-1;
        c=m;
        break;
    case 2:
        a=0; b=m;
        c=n;
        break;
    default:
        a=m-1; b=-1;
        c=n;
    }

    fr(j,c)
    {
        col[j]=0;
    }

    for(int i=a;i!=b;i=i+1-(2)*(a>b))
    {
        fr(j,c)
        {
            bool nt=side>1?mt[j][i]:mt[i][j];
            col[j]=(col[j]+nt)*nt;
        }
        if(i!=a) v[i]=max(v[a>b?i+1:i-1], beach(c));
        else v[i]=beach(c);
    }
}

int ans()
{
    int up[nmax],dwn[nmax],lef[nmax],rig[nmax];
    solveside(up,0);
    solveside(dwn,1);
    solveside(lef,2);
    solveside(rig,3);
    int mx=dwn[0];
    fr(i,n-1)
    {
        mx=max(mx,up[i]+dwn[i+1]);
    }
    mx=max(mx,up[n-1]);

    mx=max(mx,lef[0]);
    fr(i,m-1)
    {
        mx=max(mx,lef[i]+rig[i+1]);
    }
    mx=max(mx,lef[m-1]);
    return mx;
}
int main()
{
    f>>n>>m;
    string a;
    fr(i,n)
    {
        f>>a;
        fr(j,m)
        {
            mt[i][j]=(a[j]=='0');
            //cout<<mt[i][j]<<' ';
        }
        //cout<<'\n';
    }
    g<<ans()<<'\n';
    return 0;
}