Cod sursa(job #1750979)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 31 august 2016 15:35:00
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.48 kb
#include<stdio.h>
#include<vector>

using namespace std;

FILE *in, *out;

struct cladire
{
    int h, w;
};

char v[210][210];
int unu[210][210];
cladire drebun[2][205];

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 caz)
{
    int i, j, nn, mm, aux, gay[210][210];
    nn = *a;
    mm = *b;

    if(caz == 0) {
        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];
            }
        }
    } else {
        for(i = 0; i <= nn + 1; i++) {
            for(j = 0; j <= mm + 1; j++) {
                gay[j][nn + 1 - i] = unu[i][j];
            }
        }
        for(i = 0; i <= mm + 1; i++) {
            for(j = 0; j <= nn + 1; j++) {
                unu[i][j] = gay[i][j];
            }
        }
    }
    *a = *b;
    *b = nn;
}

void printfa(int n, int m)
{
    int i, j;

    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");
    printf("\n");
    printf("\n");
}

int corectie(int h, int cur, int va)
{
    if(h <= cur - va) {
        return h;
    } else {
        return cur - va;
    }
}
void calcbun(int n, int m, int poz)
{
    int fns = -1;
    cladire cresc[205];
    int i, j, l, maxu, maxd, maxt, x, scoase, maxh;


    for(i = 1; i <= n; i++) {
        maxt = 0;
        maxh = 0;
        for(j = 1; j <= m + 1; j++) {
            if(fns == -1 || (unu[i][j] >= cresc[fns].h)) {
                cladire aux;
                aux.h = unu[i][j];
                aux.w = 1;
                cresc[fns + 1] = aux;
                fns++;
            } else {
                scoase = 0;
                do {
                    x = cresc[fns].h;
                    scoase = scoase + cresc[fns].w;
                    fns--;
                    if(x * scoase > maxt) {
                        maxt = x * scoase;
                        maxh = x;
                    }
                }
                while(fns != -1 && cresc[fns].h > unu[i][j]);
                cladire aux;
                aux.h = unu[i][j];
                aux.w = 1 + scoase;
                cresc[fns + 1] = aux;
                fns++;
            }

        }
        if(maxh != 0) {
            drebun[poz][i].h = maxh;
            drebun[poz][i].w = maxt / maxh;
        } else {
            drebun[poz][i].h = 0;
            drebun[poz][i].w = 0;
        }
        //printf("%d %d %d\n", i, drebun[poz][i].h, drebun[poz][i].w);
        fns = -1;
    }
}

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

    //int fns = -1;
    //vector<cladire> cresc;
    //cresc.reserve(203);

    precalc(n, m);
    //printfa(n, m);
    calcbun(n, m, 0);
    turn(&n, &m, 0);
    turn(&n, &m, 0);
    precalc(n, m);
    turn(&n, &m, 1);
    turn(&n, &m, 1);
    //printfa(n, m);
    calcbun(n, m, 1);

    maxt = 0;
    for(l = 1; l < n; l++) {
        maxu = 0;
        for(i = 1; i <= l; i++) {
            cur = drebun[0][i].h * drebun[0][i].w;
            if(cur > maxu) {
                maxu = cur;
            }
        }
        maxd = 0;
        for(i = l + 1; i <= n; i++) {
            cur = drebun[1][i].h * drebun[1][i].w;
            if(cur > maxd) {
                maxd = cur;
            }
        }
        cur = maxu + maxd;
        if(cur > maxt) {
            maxt = cur;
        }
    }

    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;
        }
    }

    int max1, max2;

    max1 = opti(n, m);
    turn(&n, &m, 0);

    max2 = opti(n, m);

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

    fclose(in);
    fclose(out);

    return 0;
}