Cod sursa(job #1842380)

Utilizator edicCiuculescu Eduard edic Data 6 ianuarie 2017 21:23:42
Problema BMatrix Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int ma[203][203],aux[203][203],st[202],dr[202],up[203],c[202][202],steve[203];
char s[203];
void flip(int &n,int &m)
{
    int i,j,au=n;
    n=m;
    m=au;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            aux[i][j]=ma[j][n-i+1];
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            ma[i][j]=aux[i][j];
        }
    }
}
void gen(int n,int m)
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            c[i][j]=(c[i-1][j]+1)*((ma[i][j]+1)%2);
        }
    }
}
void builst(int i,int m)
{
    int h=0;
    steve[0]=0;
    for(int j=1;j<=m;j++)
    {
        while(c[i][j]<=c[i][steve[h]]&&h>0)
        {
            h--;
        }
        st[j]=steve[h];
        h++;
        steve[h]=j;
    }
}
void buildr(int i,int m)
{
    int h=0;
    steve[0]=m+1;
    for(int j=m;j>=1;j--)
    {
        while(c[i][j]<=c[i][steve[h]]&&h>0)
        {
            h--;
        }
        dr[j]=steve[h];
        h++;
        steve[h]=j;
    }
}
int solve(int n,int m)
{
    int i,j,mas=0;
    gen(n,m);
    for(i=1;i<n;i++)
    {
        builst(i,m);
        buildr(i,m);
        for(j=1;j<=m;j++)
        {
            if(c[i][j]*(dr[j]-st[j]-1)>up[i])
                up[i]=c[i][j]*(dr[j]-st[j]-1);
        }
    }
    flip(n,m);
    flip(n,m);
    gen(n,m);
    for(i=1;i<=n;i++)
    {
        builst(i,m);
        buildr(i,m);
        for(j=1;j<=m;j++)
        {
            if(c[i][j]*(dr[j]-st[j]-1)+up[n-i]>mas)
                mas=c[i][j]*(dr[j]-st[j]-1)+up[n-i];
        }
    }
    for(i=1;i<=n;i++)
    {
        up[i]=0;
    }
    return mas;
}
int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    int n,m,i,j,au,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%s",&s);
        for(j=1;j<=m;j++)
        {
            ma[i][j]=s[j-1]-'0';
        }
    }
    a=solve(n,m);
    flip(n,m);
    b=solve(n,m);
    printf("%d",max(a,b));
    return 0;
}