Cod sursa(job #2430413)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 14 iunie 2019 17:47:01
Problema BMatrix Scor 4
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <bits/stdc++.h>
#define Dim 205
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int N,M,dp[5][Dim][Dim][Dim],B1[Dim][Dim],B2[Dim][Dim],B3[Dim][Dim],B4[Dim][Dim],V[6],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 h=1;i+h-1<=N;h++)
    if(A[i+h-1][j]=='0')
    {
        dp[1][i][j][h]=dp[1][i][j+1][h]+h;
        B4[i][j]=max(max(B4[i+1][j+1],B4[i+1][j]),max(B4[i][j+1],dp[1][i][j][h]));
    }
    else
    {
        if(h==1)
        B4[i][j]=max(max(B4[i+1][j+1],B4[i+1][j]),max(B4[i][j+1],dp[1][i][j][h]));
        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]=dp[2][i][j-1][k]+k-reper;
        B1[i][j]=max(max(B1[i-1][j],B1[i-1][j-1]),max(B1[i][j-1],dp[2][i][j][k]));
    }
    else
    {
        if(k==1)
        B1[i][j]=max(max(B1[i-1][j],B1[i-1][j-1]),max(B1[i][j-1],dp[2][i][j][k]));
        reper=k;

    }

    }


    for(int i=1;i<=N;i++)
    for(int j=M;j>=1;j--)
    {

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

    }

    }

    for(int i=N;i>=1;i--)
    for(int j=1;j<=M;j++)
    {

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

    }

    //for(int i=1;i<=N;i++,cout<<'\n')
      //  for(int j=1;j<=M;j++) cout<<B3[i][j]<<" ";//<<" "<<B2[i][j+1]<<" "<<B3[i+1][j]<<" "<<B4[i+1][j+1]<<" "<<i<<" "<<j<<'\n';

    for(int i=1;i<=N;i++)
    for(int j=1;j<=M;j++)
    {
        V[1]=B1[i][j],V[2]=B2[i][j],V[3]=B3[i][j],V[4]=B4[i][j];

        sort(V+1,V+4);//cout<<i<<" "<<j<<" "<<V[3]<<" "<<V[4]<<'\n';
        ans=max(ans,V[3]+V[4]);
    }
    g<<ans;
    return 0;
}