Cod sursa(job #1840686)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 4 ianuarie 2017 18:46:48
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[205][205];
void rot(int &n,int &m)
{
    int i,j,aux[205][205];
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            aux[j][n-i+1]=a[i][j];
    swap(n,m);
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            a[i][j]=aux[i][j];
}
int up[205],down[205],c[205][205];
int soldiers_row(int a[205],int n)
{
    int i,st[205],k;
    int l[205],r[205];
    k=0;
    st[0]=0;
    for(i=1; i<=n; i++)
    {
        while(k>0 && a[st[k]]>=a[i]) k--;
        l[i]=st[k];
        st[++k]=i;
    }
    k=0;
    st[0]=n+1;
    for(i=n; i>=1; i--)
    {
        while(k>0 && a[st[k]]>=a[i]) k--;
        r[i]=st[k];
        st[++k]=i;
    }
    int ans=0;
    for(i=1; i<=n; i++)
        ans=max(ans,a[i]*(r[i]-l[i]-1));
    return ans;
}
void get_up(int n,int m,int up[205])
{
    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            if(a[i][j]==1) c[i][j]=0;
            else c[i][j]=c[i-1][j]+1;
        }
    for(i=1; i<=n; i++)
        up[i]=max(up[i-1],soldiers_row(c[i],m));
}
int solve(int n,int m)
{
    int i;
    get_up(n,m,up);
    rot(n,m);
    rot(n,m);
    get_up(n,m,down);
    reverse(down+1,down+n+1);
    int ans=0;
    for(i=1; i<n; i++)
        ans=max(ans,up[i]+down[i+1]);
    return ans;
}
int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    int i,j;
    char s[105];
    scanf("%d%d\n",&n,&m);
    for(i=1; i<=n; i++)
    {
        gets(s);
        for(j=1; j<=m; j++)
            a[i][j]=s[j-1]-'0';
    }
    int ans;
    ans=solve(n,m);
    rot(n,m);
    ans=max(ans,solve(n,m));
    printf("%d\n",ans);
    return 0;
}