Cod sursa(job #1750357)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 29 august 2016 22:43:12
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.21 kb
#include<stdio.h>
#include<vector>

using namespace std;

FILE *in, *out;

char v[210][210];
int unu[210][210];

void precalc(int a, int b)
{
    int i, j;

    for(i = 0; i <= a + 1; i++) {
        for(j = 0; j <= b + 1; j++) {
            if(v[i][j] == 1) {
                unu[i][j] = unu[i - 1][j] + 1;
            } else {
                unu[i][j] = 0;
            }
        }
    }
}

void turn(int *a, int *b)
{
    int i, j, nn, mm, aux, gay[210][210];
    nn = *a;
    mm = *b;

    for(i = 0; i <= nn + 1; i++) {
        for(j = 0; j <= mm + 1; j++) {
            gay[j][nn + 1 - i] = v[i][j];
        }
    }
    for(i = 0; i <= mm + 1; i++) {
        for(j = 0; j <= nn + 1; j++) {
            v[i][j] = gay[i][j];
        }
    }
    *a = *b;
    *b = nn;
}

struct cladire
{
    int h, w;
};

int corectie(int h, int cur, int va)
{
    if(h <= cur - va) {
        return h;
    } else {
        return cur - va;
    }
}

int opti(int n, int m)
{
    int i, j, l, maxu, maxd, maxt, x, scoase;

    vector<cladire> cresc;
    maxt = 0;
    for(l = 1; l < n; l++) {
        maxu = 0;
        maxd = 0;
        for(i = 1; i <= l; i++) {
            for(j = 1; j <= m + 1; j++) {
                if(cresc.empty() || (unu[i][j] >= cresc.back().h)) {
                    cladire aux;
                    aux.h = unu[i][j];
                    aux.w = 1;
                    cresc.push_back(aux);
                } else {
                    scoase = 0;
                    do {
                        x = cresc.back().h;
                        scoase = scoase + cresc.back().w;
                        cresc.pop_back();
                        if(x * scoase > maxu) {
                            maxu = x * scoase;
                        }
                    }
                    while(!(cresc.empty()) && cresc.back().h > unu[i][j]);
                    cladire aux;
                    aux.h = unu[i][j];
                    aux.w = 1 + scoase;
                    cresc.push_back(aux);
                }

            }
            while(!cresc.empty()) {
                cresc.pop_back();
            }
        }
        for(i = l + 1; i <= n; i++) {
            for(j = 1; j <= m + 1; j++) {
                if(cresc.empty() || (corectie(unu[i][j], i, l) >= cresc.back().h)) {
                    cladire aux;
                    aux.h = corectie(unu[i][j], i, l);
                    aux.w = 1;
                    cresc.push_back(aux);
                } else {
                    scoase = 0;
                    do {
                        x = cresc.back().h;
                        scoase = scoase + cresc.back().w;
                        cresc.pop_back();
                        if(x * scoase > maxd) {
                            maxd = x * scoase;
                        }
                    }
                    while(!(cresc.empty()) && cresc.back().h > corectie(unu[i][j], i, l));
                    cladire aux;
                    aux.h = corectie(unu[i][j], i, l);
                    aux.w = 1 + scoase;
                    cresc.push_back(aux);
                }

            }
            while(!cresc.empty()) {
                cresc.pop_back();
            }
        }
        if(maxu + maxd > maxt) {
            maxt = maxu + maxd;
        }
    }

    return maxt;
}

int main ()
{

    int n, m, i, j;

    in = fopen("bmatrix.in", "r");
    out = fopen("bmatrix.out", "w");

    fscanf(in, "%d%d", &n, &m);

    for(i = 1; i <= n; i++) {
        fscanf(in, "%s", &v[i][1]);
    }
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            v[i][j] -= '0';
            v[i][j] = (v[i][j] + 1) & 1;
        }
    }
/*
    for(i = 0; i <= n + 1; i++) {
        for(j = 0; j <= m + 1; j++) {
            printf("%d ", v[i][j]);
        }
        printf("\n");
    }

    printf("\n");

    for(i = 0; i <= n + 1; i++) {
        for(j = 0; j <= m + 1; j++) {
            printf("%d ", unu[i][j]);
        }
        printf("\n");
    } printf("\n");
*/
    int max1, max2;

    precalc(n, m);
    max1 = opti(n, m);

    turn(&n, &m);
    precalc(n, m);

    max2 = opti(n, m);
    //max2 = 0;
    if(max1 > max2) {
        fprintf(out, "%d", max1);
    } else {
        fprintf(out, "%d", max2);
    }

    fclose(in);
    fclose(out);

    return 0;
}