Cod sursa(job #2863225)

Utilizator RK13Barbu Eduard RK13 Data 6 martie 2022 14:45:18
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <bits/stdc++.h>
//TBD
using namespace std;

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

int a[201][201],b[201][201],st[201],vf,dmax[4][201],n,m,d,h[201][201];

void arie()
{int s;
 for (int i=1;i<=n;i++)
   {vf=1;
    st[vf]=0;
    for (int j=1;j<=m+1;j++) {
                              while (h[i][j]<=h[i][st[vf]] && vf>=1)
                                {s=h[i][st[vf]]*(i-1-st[vf-1]);
                                                                     dmax[d][j-1]=max(dmax[d][j-1],s);
                                                                     dmax[d][st[vf]]=max(dmax[d][st[vf]],h[i][st[vf]]*(st[vf]-st[vf-1]));
                                                                    vf--;
                                                                    }
                              vf++;
                              st[vf]=j;

                             }
   }
for(int j=2;j<=n;j++)
        dmax[d][j]=max(dmax[d][j],dmax[d][j-1]);
}

void rotire() //rotirea matricei
{
    int i,j;
    for(i=0;i<=201;i++)
    for(j=0;j<=201;j++)
        h[i][j]=0;
    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
        b[j][m-i+1]=a[i][j];
    swap(m,n);
    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
        a[i][j]=b[i][j];
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        if(a[i][j]==0)
            h[i][j]=h[i][j-1]+1;
    }
}

int main()
{
char s[201];
for (int i=1;i<=n;i++) {cin>>s;
                        for (int j=0;j<strlen(s);j++) {a[i][j+1]=s[i]-'0';
                                                      if (a[i][j]==0) h[i][j]=h[i-1][j]+1;
                                                      }
                        }
d=0;
arie();
rotire();

d=1;
arie();
rotire();

d=2;
arie();
rotire();

d=3;
arie();
rotire();
int x,sol=-1;
for (int i=0;i<=m;i++) {x=dmax[0][i]+dmax[2][m-i];
                    sol=max(sol,x);
                   }
for (int i=0;i<=n;i++) {x=dmax[1][i]+dmax[3][n-i];
                    sol=max(sol,x);
                   }
g<<sol;
}