Cod sursa(job #935464)

Utilizator rudarelLup Ionut rudarel Data 3 aprilie 2013 15:09:07
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>
using namespace std;
 
const char iname[] = "bmatrix.in";
const char oname[] = "bmatrix.out";
const int  MaxN = 202;
 
int  n, m;
char A[MaxN][MaxN];
int  H[MaxN][MaxN], M1[MaxN][MaxN], M2[MaxN][MaxN];
int  Rez;
 
 
#define maxim(a,b) ((a) > (b) ? (a) : (b))
 
int main(void)
{
    freopen(iname, "r", stdin);
    freopen(oname, "w", stdout);
    int i, j, k;
    int hmin, max;
 
    scanf("%d %d\n", &n, &m);
    for (i = 1; i <= n; ++i)
        scanf("%s\n", A[i]+1);
 
    /* de sus in jos */
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= m; ++j)
            H[i][j] = (A[i][j] == '0') ? H[i-1][j] + 1 : 0;
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= m; ++j) {
            for (k = j, max = 0, hmin = MaxN; k > 0; --k) {
                if (hmin > H[i][k])
                    hmin = H[i][k];
                if (max < (j-k+1) * hmin)
                    max = (j-k+1) * hmin;
            }
            M1[i][j] = max;
            M1[i][m+1] = maxim(M1[i][m+1], maxim(max, M1[i-1][m+1]));
            M1[n+1][j] = maxim(M1[n+1][j], maxim(max, M1[n+1][j-1]));
        }
 
    /* de jos in sus */
    for (i = n; i >= 1; --i)
        for (j = 1; j <= m; ++j)
            H[i][j] = (A[i][j] == '0') ? H[i+1][j] + 1 : 0;
    for (i = n; i >= 1; --i)
        for (j = m; j >= 1; --j) {
            for (k = j, max = 0, hmin = MaxN; k <= m; ++k) {
                if (hmin > H[i][k])
                    hmin = H[i][k];
                if (max < (k-j+1) * hmin)
                    max = (k-j+1) * hmin;
            }
            M2[i][j] = max;
            M2[i][0] = maxim(M2[i][0], maxim(max, M2[i+1][0]));
            M2[0][j] = maxim(M2[0][j], maxim(max, M2[0][j+1]));
    }
     
    /* desparte dreptunghiurile pe verticala */
    for (j = 1; j < m; ++j)
        if (Rez < M1[n+1][j] + M2[0][j+1])
            Rez = M1[n+1][j] + M2[0][j+1];
    for (i = 1; i < n; ++i)
        if (Rez < M1[i][m+1] + M2[i+1][0])
            Rez = M1[i][m+1] + M2[i+1][0];
    printf("%d\n", Rez);
 
    return 0;
}