Cod sursa(job #1841935)

Utilizator PondorastiAlex Turcanu Pondorasti Data 6 ianuarie 2017 12:19:31
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[255][255];
void rot(int &n,int &m)
{
    int i,j,aux[255][255];
    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[255],down[255],c[255][255],l[255],r[255],st[255];
int soldiers_row(int a[255],int n)
{
    int i,k;
    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[250])
{
    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[255];
    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;
}