Cod sursa(job #1711454)

Utilizator cristina_borzaCristina Borza cristina_borza Data 31 mai 2016 11:56:12
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.6 kb
#include <fstream>
#include <cstring>

#define DIM 205

using namespace std;

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

short int dp1[DIM][DIM][DIM] , dp2[DIM][DIM][DIM] , lastst[DIM][DIM] , lastdr[DIM][DIM] , ans1[DIM][DIM] , ans2[DIM][DIM];
short int n , m , sol;

char mat[DIM][DIM];

int min(short int a , short int b) {
    if(a < b)
        return a;
    return b;
}


int max(short int a , short int b) {
    if(a > b)
        return a;
    return b;
}

int main() {
    f >> n >> m;
    for(short int i = 1 ; i <= n ; ++i) {
        f >> mat[i] + 1;
    }

    for(short int i = 1 ; i <= n ; ++i) {
        for(short int j = 1 ; j <= m ; ++j) {
            if(mat[i][j] == '1') {
                lastst[i][j] = 0;
            }

            else {
                lastst[i][j] = lastst[i][j - 1] + 1;
            }
        }

        for(short int j = m ; j >= 1 ; --j) {
            if(mat[i][j] == '1') {
                lastdr[i][j] = 0;
            }

            else {
                lastdr[i][j] = lastdr[i][j + 1] + 1;
            }
        }
    }

    for(short int i = 1 ; i <= n ; ++i) {
        for(short int j = 1 ; j <= m ; ++j) {
            for(short int k = 2 ; k <= i ; ++k) {
                dp1[i][j][k] = min(dp1[i - 1][j][k - 1] , lastst[i][j]);
                ans1[i][j] = max(ans1[i][j] , dp1[i][j][k] * k);
            }

            dp1[i][j][1] = lastst[i][j];
            ans1[i][j] = max(ans1[i][j] , dp1[i][j][1]);

            ans1[i][j] = max(ans1[i][j] , max(ans1[i - 1][j] , ans1[i][j - 1]));
        }
    }

    for(short int i = n ; i >= 1 ; --i) {
        for(short int j = m ; j >= 1; --j) {
            for(short int k = 2 ; k <= n - i + 1 ; ++k) {
                dp2[i][j][k] = min(dp2[i + 1][j][k - 1] , lastdr[i][j]);
                ans2[i][j] = max(ans2[i][j] , dp2[i][j][k] * k);
            }

            dp2[i][j][1] = lastdr[i][j];
            ans2[i][j] = max(ans2[i][j] , dp2[i][j][1]);


            ans2[i][j] = max(ans2[i][j] , max(ans2[i + 1][j] , ans2[i][j + 1]));
        }
    }

    for(short int lin = 1 ; lin < n ; ++lin) {
        short int s1 = ans1[lin][m];
        short int s2 = ans2[lin + 1][1];
        sol = max(sol , s1 + s2);
    }

    memset(ans1 , 0 , sizeof(ans1));
    memset(ans2 , 0 , sizeof(ans2));
    memset(dp1 , 0 , sizeof(dp1));
    memset(dp2 , 0 , sizeof(dp2));

    for(short int i = 1 ; i <= n ; ++i) {
        for(short int j = m ; j >= 1 ; +--j) {
            for(short int k = 2 ; k <= i ; ++k) {
                dp1[i][j][k] = min(dp1[i - 1][j][k - 1] , lastdr[i][j]);
                ans1[i][j] = max(ans1[i][j] , dp1[i][j][k] * k);
            }

            dp1[i][j][1] = lastdr[i][j];
            ans1[i][j] = max(ans1[i][j] , dp1[i][j][1]);

            ans1[i][j] = max(ans1[i][j] , max(ans1[i - 1][j] , ans1[i][j + 1]));
        }
    }

    for(short int i = n ; i >= 1 ; --i) {
        for(short int j = 1 ; j <= m; ++j) {
            for(short int k = 2 ; k <= n - i + 1 ; ++k) {
                dp2[i][j][k] = min(dp2[i + 1][j][k - 1] , lastst[i][j]);
                ans2[i][j] = max(ans2[i][j] , dp2[i][j][k] * k);
            }

            dp2[i][j][1] = lastst[i][j];
            ans2[i][j] = max(ans2[i][j] , dp2[i][j][1]);


            ans2[i][j] = max(ans2[i][j] , max(ans2[i + 1][j] , ans2[i][j - 1]));
        }
    }

    for(short int col = 1 ; col < m ; ++col) {
        short int s1 = ans2[1][col + 1];
        short int s2 = ans1[col][n];
        sol = max(sol , s1 + s2);
    }

    g << sol;
    return 0;
}