Cod sursa(job #2430428)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 14 iunie 2019 20:08:49
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <bits/stdc++.h>
#define Dim 205
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int N,M,dp[6][Dim][Dim][Dim],B[6][Dim],ans;
char A[Dim][Dim];


int main()
{
    f>>N>>M; f.get();
    for(int i=1;i<=N;i++,f.get())
    for(int j=1;j<=M;j++) f>>A[i][j];

    for(int i=N;i>=1;i--)
    {
        int reper=0;
        for(int j=M;j>=1;j--)
        if(A[i][j]=='0')
        {
            reper++;
            for(int k=1;k<=reper;k++)
            dp[1][i][j][k]=dp[1][i+1][j][k]+k,
            B[1][i]=max(B[1][i],max(B[1][i+1],dp[1][i][j][k]));
        }
        else
        {
            B[1][i]=max(B[1][i],B[1][i+1]);
            reper=0;
        }
    }

    for(int i=1;i<=N;i++)
    {
        int reper=0;
        for(int j=1;j<=M;j++)
        if(A[i][j]=='0')
        {
            reper++;
            for(int k=1;k<=reper;k++)
            dp[2][i][j][k]=dp[2][i-1][j][k]+k,
            B[2][i]=max(B[2][i],max(B[2][i-1],dp[2][i][j][k]));
        }
        else
        {
            B[2][i]=max(B[2][i],B[2][i-1]);
            reper=0;
        }
    }

    for(int j=1;j<=M;j++)
    {
        int reper=0;
        for(int i=1;i<=N;i++)
        if(A[i][j]=='0')
        {
           reper++;
           for(int k=1;k<=reper;k++)
           dp[3][i][j][k]=dp[3][i][j-1][k]+k,
           B[3][j]=max(B[3][j],max(B[3][j-1],dp[3][i][j][k]));
        }
        else
        {
            B[3][j]=max(B[3][j],B[3][j-1]);
            reper=0;
        }
    }

    for(int j=M;j>=1;j--)
    {
        int reper=0;
        for(int i=1;i<=N;i++)
        if(A[i][j]=='0')
        {
            reper++;
            for(int k=1;k<=reper;k++)
            dp[4][i][j][k]=dp[4][i][j+1][k]+k,
            B[4][j]=max(B[4][j],max(B[4][j+1],dp[4][i][j][k]));
        }
        else
        {
            B[4][j]=max(B[4][j],B[4][j+1]);
            reper=0;
        }
    }//cout<<'\n'<<'\n'<<dp[1][6][1][2]<<'\n';
   // cout<<B[2][6]<<" "<<dp[1][1][3][2]<<'\n';

    for(int i=1;i<N;i++) ans=max(ans,B[2][i]+B[1][i+1]); //cout<<B[2][i]<<" "<<B[1][i+1]<<" "<<i<<'\n';}
    for(int j=1;j<M;j++) ans=max(ans,B[3][j]+B[4][j+1]);
    g<<ans;

    return 0;
}