Cod sursa(job #2430420)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 14 iunie 2019 19:16:59
Problema BMatrix Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 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--)
    for(int j=M;j>=1;j--)
    for(int k=1;i+k-1<=N;k++)
    if(A[i+k-1][j]=='0')
    {
        dp[1][i][j][k]=dp[1][i][j+1][k]+k;
        B[1][i]=max(B[1][i+1],dp[1][i][j][k]);
    }
    else break;

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

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

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

    for(int i=1;i<N;i++) ans=max(ans,B[2][i]+B[1][i+1]);
    for(int j=1;j<M;j++) ans=max(ans,B[3][j]+B[4][j+1]);
    g<<ans;

    return 0;
}