Cod sursa(job #2500497)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 28 noiembrie 2019 04:44:25
Problema BMatrix Scor 96
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
char a[202][202];
int h[202][202],u[202],d[202];
int f(bool b,int n,int m)
{
    int i,j,l,k;
    for(i=1;i<=n;u[i]=d[i]=0,i++)
        for(j=1;j<=m;j++)
            h[i][j]=a[b?i:j][b?j:n-i+1]*(h[i-1][j]+1);
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
            for(l=0,k=1;k<=m;k++)
                if(h[j][k]>j-i)
                {
                    l++;
                    u[j]=max(u[j],l*(j-i+1));
                    d[i]=max(d[i],l*(j-i+1));
                }
                else l=0;
        u[i]=max(u[i],u[i-1]);
        d[n-i+1]=max(d[n-i+1],d[n-i+2]);
    }
    for(i=1,l=0;i<n;i++)
        l=max(l,u[i]+d[i+1]);
    return l;
}
int main()
{
    int n,m,i,j;
    in>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            in>>a[i][j],a[i][j]='1'-a[i][j];
    out<<max(f(1,n,m),f(0,m,n));
    return 0;
}