Cod sursa(job #1678724)

Utilizator RadduFMI Dinu Radu Raddu Data 7 aprilie 2016 15:12:35
Problema BMatrix Scor 92
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

int k,q[205],n,m,a[205][205],b[205][205],csus[205][205],cjos[205][205],st[205],dr[205],vsus[205][205],vjos[205][205];
int mxsus[205],mxjos[205],sol,sol1,sol2;

void Solve(int caz)
{ int i,j,mx=0;
   for(i=1;i<=n;i++)
     for(j=1;j<=m;j++)
      if (!a[i][j]) csus[i][j]=csus[i-1][j]+1;


    for(i=n;i>=1;i--)
     for(j=1;j<=m;j++)
      if (!a[i][j]) cjos[i][j]=cjos[i+1][j]+1;



 for(i=1;i<=n;i++)
  {
    k=0;
    for(j=1;j<=m;j++)
    { while(k && csus[i][q[k]]>=csus[i][j])
        k--;
      if (!k) st[j]=1; else st[j]=q[k]+1;
        k++; q[k]=j;
    }

    k=0;
    for(j=m;j>=1;j--)
    { while(k && csus[i][q[k]]>=csus[i][j])
        k--;
      if (!k) dr[j]=m; else dr[j]=q[k]-1;
        k++; q[k]=j;
    }

    for(j=1;j<=m;j++)
     vsus[i][j]=(dr[j]-st[j]+1)*csus[i][j];
  }

  for(i=1;i<=n;i++)
  {
    k=0;
    for(j=1;j<=m;j++)
    { while(k && cjos[i][q[k]]>=cjos[i][j])
        k--;
      if (!k) st[j]=1; else st[j]=q[k]+1;
        k++; q[k]=j;
    }

    k=0;
    for(j=m;j>=1;j--)
    { while(k && cjos[i][q[k]]>=cjos[i][j])
        k--;
      if (!k) dr[j]=m; else dr[j]=q[k]-1;
        k++; q[k]=j;
    }

    for(j=1;j<=m;j++)
     vjos[i][j]=(dr[j]-st[j]+1)*cjos[i][j];
  }

mx=0;
 for(i=1;i<=n;i++)
  {for(j=1;j<=n;j++)
    mx=max(mx,vsus[i][j]);
     mxsus[i]=mx;
  }
   mx=0;
 for(i=n;i>=1;i--)
  {for(j=1;j<=n;j++)
    mx=max(mx,vjos[i][j]);
    mxjos[i]=mx;
  }

  for(i=1;i<n;i++)
   if (mxsus[i]>0 && mxjos[i+1]>0)
    { if (caz==1) sol1=max(sol1,mxsus[i]+mxjos[i+1]);
       else sol2=max(sol2,mxsus[i]+mxjos[i+1]);
    }
}

void Roteste()
{ int i,j,l=0,c=0;

    for(i=n;i>=1;i--)
    { c++;
        for(j=1;j<=m;j++)
         b[j][c]=a[i][j];
    }

  swap(n,m);
  for(i=1;i<=n;i++)
   for(j=1;j<=m;j++)
    a[i][j]=b[i][j];
}
int main()
{ int i,j; char s[205];
    f>>n>>m;
    for(i=1;i<=n;i++)
     { f>>s;
         for(j=1;j<=m;j++)
           a[i][j]=s[j-1]-48;
     }

   Solve(1);

   Roteste();

   memset(st,0,sizeof(st));
   memset(dr,0,sizeof(dr));
   memset(cjos,0,sizeof(cjos));
   memset(csus,0,sizeof(csus));
   memset(mxjos,0,sizeof(mxjos));
   memset(mxsus,0,sizeof(mxsus));
   memset(vjos,0,sizeof(vjos));
   memset(vsus,0,sizeof(vsus));

   Solve(2);

   sol=max(sol1,sol2);

   g<<sol;

    return 0;
}