Cod sursa(job #2009268)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 9 august 2017 04:41:19
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.31 kb
#include<fstream>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int INF =1000;
int times,k,n,m,i,j;
int maxim_orizontal_sus,maxim_orizontal_jos,maxim_vertical_stanga, maxim_vertical_dreapta;
int maxim_vertical, maxim_orizontal;
int tablou[2][201][201], sumcol[201][201],stiva[201],biggest[5][201],stanga[201],dreapta[201];
char q;
int main(){
    in >> n >> m;
    for( i = 1; i <= n; i ++ ){
        for( j = 1; j <= m; j ++ ){
            in >> q;
            if( q == '1' ){
                tablou[0][i][j] = -INF;
            }
            else{
                tablou[0][i][j] = 0;
            }
        }
    }
    for( times = 0; times < 4; times ++ ){
        for( j = 1; j <= m; j ++ ){
            for( i = 1; i <= n; i ++ ){
                if( tablou[times%2][i][j] != -INF ){
                    if( sumcol[i-1][j] > 0 ){
                        sumcol[i][j] = sumcol[i-1][j] + 1;
                    }
                    else{
                        sumcol[i][j] = 1;
                    }
                }
                else{
                    sumcol[i][j] = 0;
                }
            }
        }
        for( i = 1; i <= n; i ++ ){
            k = 0;
            for( j = 1; j <= m; j ++ ){
                while( k > 0 and sumcol[i][stiva[k]] >= sumcol[i][j] ){
                    k--;
                }
                stanga[j] = stiva[k];
                k++; stiva[k] = j;
            }
            k = 0;
            for( j = m; j >= 1; j -- ){
                while( k > 0 and sumcol[i][stiva[k]] >= sumcol[i][j] ){
                    k--;
                }
                dreapta[j] = stiva[k];
                k++; stiva[k] = j;
            }
            stanga[1] = 0; dreapta[m] = m+1;
            for( j = 1; j <= m; j ++ ){
                biggest[times+1][i] = max( biggest[times+1][i], sumcol[i][j]*( (dreapta[j]-1) - (stanga[j]+1 ) + 1 ));
            }
        }

        for( i = 1; i <= m; i ++ ){
            for( j = 1; j <= n; j ++  ){
                tablou[(times+1)%2][i][j] = tablou[times%2][j][m-i+1];
            }
        }
        swap( n,m );
    }

    for( i = 1; i <= n/2; i ++ ){
        swap( biggest[3][i], biggest[3][n-i+1] );
    }
    for( j = 1; j <= m/2; j ++ ){
        swap( biggest[4][j], biggest[4][m-j+1] );
    }



    for( k = 2; k <= m-1; k ++ ){
        maxim_vertical_stanga = 0; maxim_vertical_dreapta = 0;
        for( j = 1; j < k; j ++ ){
            maxim_vertical_stanga = max( maxim_vertical_stanga, biggest[2][j] );
        }
        for( j = k; j <= m; j ++ ){
            maxim_vertical_dreapta = max( maxim_vertical_dreapta, biggest[4][j] );
        }
        maxim_vertical = max( maxim_vertical, maxim_vertical_stanga + maxim_vertical_dreapta);
    }

    for( k = 2; k <= n-1; k ++ ){
        maxim_orizontal_sus = 0; maxim_orizontal_jos = 0;
        for( i = 1; i < k; i ++ ){
            maxim_orizontal_sus = max( maxim_orizontal_sus, biggest[1][i] );
        }
        for( i = k; i <= n; i ++ ){
            maxim_orizontal_jos = max( maxim_orizontal_jos, biggest[3][i] );
        }
        maxim_orizontal = max( maxim_orizontal_sus+ maxim_orizontal_jos,maxim_orizontal );
    }
    out<< max( maxim_orizontal,maxim_vertical );
    return 0;
}