Cod sursa(job #2228808)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 4 august 2018 21:51:21
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>
#define N 205
using namespace std;

ifstream fin("bmatrix.in") ;
ofstream fout("bmatrix.out") ;

int mat[N][N] , dp[N][N] ;
int n , m , finall = 0 ;

void dreptmax()
{
    bool v[N] ;
    int i , j , k , lgm , lgmax ;
    for ( i = 1 ; i <= n ; i++ )
    {
        memset(v,true,sizeof(v)) ;
        for ( j = i ; j <= n ; j++ )
        {
            for ( k = 1 ; k <= m ; k++ )
                v[k] = (v[k]&(1-mat[j][k])) ;
            lgm = 0 ;
            lgmax = -1 ;
            for ( k = 1 ; k <= m ; k++ )
            {
                if ( v[k] == 1 )
                    lgm++ ;
                else
                {
                    if ( lgm > lgmax )
                        lgmax = lgm ;
                    lgm = 0 ;
                }
                if ( lgm > lgmax )
                    lgmax = lgm ;
            }
            dp[i][j] = (j-i+1)*lgmax;
        }
    }

}

void raspuns()
{
    int i , j , max1 , max2 , k ;
    for ( i = 1 ; i <= n ; i++ )
    {
        max1 = -1 ;
        max2 = -1 ;
        for ( j = 1 ; j <= i ; j++ )
            for ( k = j ; k <= i ; k++ )
                if ( dp[j][k] > max1 )
                    max1 = dp[j][k] ;
        for ( j = i+1 ; j <= n ; j++ )
            for ( k = j ; k <= n ; k++ )
                if ( dp[j][k] > max2 )
                    max2 = dp[j][k] ;
        if ( max1 + max2 > finall )
        {
            finall = max1+ max2 ;
        }
    }
}

int main()
{
    int i , j ;
    char ch;
    fin >> n >> m ;
    for ( i = 1 ; i <= n ; i++ )
    {
        for ( j = 1 ; j <= m ; j++ )
        {
            fin >> ch ;
            mat[i][j] = ch - '0' ;
        }
    }
    dreptmax() ;
    raspuns() ;
    memset(dp,0,sizeof(dp)) ;
    for ( i = 1 ; i <= N-4 ; i++ )
        for ( j = i+1 ; j <= N-4 ; j++ )
           swap(mat[i][j],mat[j][i]) ;
    swap(n,m) ;
    dreptmax() ;
    raspuns() ;
    fout << finall ;
}