Cod sursa(job #2228781)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 4 august 2018 19:05:49
Problema BMatrix Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 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][3] , M1[N][N][2] ;
int n , m ;

int euclid(int a, int b)
{
    int c;
    while (b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int vizitez( int ct , int x , int y , int mx )
{
    int i , j , maxima = -1;
    int ctx = euclid(mx,dp[x-1][y][2]) ;
    int cty = mx/ctx ;
    for ( i = x ; i > x - cty ; i-- )
        for ( j = y ; j > y - ctx ; j-- )
            M1[i][j][ct] =1 ;
    /*for ( i = 1 ; i <= n ; i++ )
    {
        for ( j = 1 ; j <= m ; j++ )
            cout << M1[i][j][ct] << " " ;
        cout << endl ;
    }
    cout << endl << endl ;
*/
    for ( i = 1 ; i <= n ; i++ )
    {
        for ( j = 1 ; j <= m ; j++ )
        {
            if ( M1[i][j][ct] == 0 )
                dp[i][j][ct] = dp[i-1][j][ct]+dp[i][j-1][ct]-dp[i-1][j-1][ct]+1 ;
            maxima = max(maxima,dp[i][j][ct]) ;
        }
    }
    return maxima+mx;
}

int main()
{
    int i , j , maxim , maxim2 , m1x , m2x , m1y , m2y ;
    char ch;
    fin >> n >> m ;
    for ( i = 1 ; i <= n ; i++ )
    {
        for ( j = 1 ; j <= m ; j++ )
        {
            fin >> ch ;
            mat[i][j] = ch - '0' ;
            M1[i][j][0] = mat[i][j] ;
            M1[i][j][1] = mat[i][j] ;
        }
    }
    maxim = -1;
    for ( i = 1 ; i <= n ; i++ )
    {
        for ( j = 1 ; j <= m ; j++ )
        {
            if ( mat[i][j] == 0 )
                dp[i][j][2] = dp[i-1][j][2]+dp[i][j-1][2]-dp[i-1][j-1][2]+1 ;
            if ( maxim < dp[i][j][2] )
            {
                maxim2 = maxim ;
                m2x = m1x ;
                m2y = m1y ;
                maxim = dp[i][j][2] ;
                m1x = i ;
                m1y = j ;
            }
           // cout << dp[i][j][2] << " " ;
        }
       // cout << endl ;
    }
    //cout << maxim << " " << maxim2 << " " << m1x << " " << m1y << endl ;
    //cout << endl << endl;
    //cout << vizitez(0,m1x,m1y,maxim) << " " ;
    //cout << vizitez(1,m2x,m2y,maxim2) ;
    fout << max(vizitez(0,m1x,m1y,maxim),vizitez(1,m2x,m2y,maxim2)) ;
}