Cod sursa(job #2020888)

Utilizator Bodo171Bogdan Pop Bodo171 Data 11 septembrie 2017 22:25:50
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=205;
char s[nmax][nmax],nu[nmax][nmax];
int st[nmax],a[nmax],up[nmax],down[nmax],l[nmax],r[nmax];
int n,m,mx,i,j,u;
void build_dp(bool what)
{
        u=0;st[0]=0;
        for(j=1;j<=m;j++)
        {
            a[j]=(a[j]+1)*(s[i][j]=='0');
            while(u>0&&a[j]<=a[st[u]])
                u--;
            l[j]=st[u];
            u++;st[u]=j;
        }
        u=0;st[0]=m+1;
        for(j=m;j>=1;j--)
        {
            while(u>0&&a[j]<a[st[u]])
                u--;
            r[j]=st[u];
            u++;st[u]=j;
        }
        for(j=1;j<=m;j++)
        {
            if(what==0&&(r[j]-l[j]-1)*a[j]>up[i])
                up[i]=(r[j]-l[j]-1)*a[j];
            if(what==1&&(r[j]-l[j]-1)*a[j]>down[i])
                down[i]=(r[j]-l[j]-1)*a[j];
        }
}
void solve()
{
    for(i=0;i<=n+1;i++)
        up[i]=0;
    for(i=1;i<=m;i++)
        a[i]=0;
      for(i=1;i<=n;i++)
    {
      build_dp(0);
    }
     for(i=0;i<=n+1;i++)
        down[i]=0;
    for(i=1;i<=m;i++)
        a[i]=0;
      for(i=n;i>=1;i--)
    {
       build_dp(1);
    }
    for(i=1;i<=n;i++)
        up[i]=max(up[i],up[i-1]);
    for(i=n;i>=1;i--)
        down[i]=max(down[i],down[i+1]);
    for(i=1;i<=n;i++)
        if(up[i]+down[i+1]>mx)
            mx=up[i]+down[i+1];
}
int main()
{
    ifstream f("bmatrix.in");
    ofstream g("bmatrix.out");
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
          f>>s[i][j];
    solve();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
          nu[j][i]=s[i][j];
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
          s[i][j]=nu[i][j];
    swap(n,m);
    solve();
    g<<mx;
    return 0;
}