Cod sursa(job #2027983)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 26 septembrie 2017 22:28:03
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n,m,i,j,k,ult,fr[1<<8],D[1<<8],up[1<<8],down[1<<8],Left[1<<8],Right[1<<8];
char M[1<<8][1<<8];
int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i) f>>(M[i]+1);
    for(i=1;i<=n;++i)
    {
        k=D[0]=0;
        for(j=1;j<=m;++j)
        {
            if(M[i][j]=='0') C[i][j]=C[i-1][j]+1;
            while(k&&C[i][D[k]]>=C[i][j]) --k;
            Cur[j]=j-D[k];
        }
        k=0;
        D[0]=m+1;
        for(j=m;j>0;--j)
        {
            while(k&&C[i][D[k]]>=C[i][j]) --k;
            Cur[j]+=D[k]-j-1;
        }
        for(j=1;j<=m;++j)
        {
            Left[i]=max(Left[i],max(Left[i-1],Cur[j]*C[i][j]));
            up[j]=max(up[j],max(up[j-1],Cur[j]*C[i][j]));
        }
    }
    for(i=1;i<=m;++i) fr[i]=0;
    int sol=0;
    for(i=1;i<n;++i) sol=max(sol,Left[i]+Right[i+1]);
    for(i=1;i<m;++i) sol=max(sol,up[i]+down[i+1]);
    g<<sol;
    return 0;
}