Cod sursa(job #3365912)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 27 septembrie 2026 18:34:40
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.52 kb
#include <iostream>

const int MAX = 200;
char mr[MAX + 2][MAX + 2];
int nrs[MAX + 2][MAX + 2], nrj[MAX + 2][MAX + 2], nrst[MAX + 2][MAX + 2], nrdr[MAX + 2][MAX + 2], vst[MAX + 2], vdr[MAX + 2], st[MAX + 1];
int maxpl[MAX + 2], maxpc[MAX + 2], maxsl[MAX + 2], maxsc[MAX + 2];
int maxim(int a, int b) {
    return a > b ? a : b;
}
int main()
{
    FILE *fin, *fout;
    //O(n * m)
    //cele 2 dreptunghiuri nu vor avea nicio linie in comun sau nicio coloana in comun
    int n, m, l, c, vf, rez;
    fin = fopen("bmatrix.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for (l = 1; l <= n; l++) {
        fscanf(fin, " ");
        for (c = 1; c <= m; c++) {
            mr[l][c] = '1' - fgetc(fin);
            if (mr[l][c] > 0) {
                nrst[l][c] = nrst[l][c - 1] + 1;
                nrs[l][c] = nrs[l - 1][c] + 1;
            }
        }
    }
    fclose(fin);
    for (l = n; l > 0; l--) {
        for (c = m; c > 0; c--) {
            if (mr[l][c] > 0) {
                nrdr[l][c] = nrdr[l][c + 1] + 1;
                nrj[l][c] = nrj[l + 1][c] + 1;
            }
        }
    }
    for (l = 1; l <= n; l++) {
        vf = 0;
        st[0] = 0;
        nrs[l][0] = -1;
        for (c = 1; c <= m; c++) {
            while (nrs[l][c] <= nrs[l][st[vf]]) {
                vf--;
            }
            vst[c] = st[vf];
            vf++;
            st[vf] = c;
        }
        vf = 0;
        st[0] = m + 1;
        nrs[l][m + 1] = -1;
        for (c = m; c > 0; c--) {
            while (nrs[l][c] <= nrs[l][st[vf]]) {
                vf--;
            }
            vdr[c] = st[vf];
            vf++;
            st[vf] = c;
        }
        for (c = 1; c <= m; c++) {
            maxpl[l] = maxim(maxpl[l], (vdr[c] - vst[c] - 1) * nrs[l][c]);
        }
        maxpl[l] = maxim(maxpl[l], maxpl[l - 1]);



        vf = 0;
        st[0] = 0;
        nrj[l][0] = -1;
        for (c = 1; c <= m; c++) {
            while (nrj[l][c] <= nrj[l][st[vf]]) {
                vf--;
            }
            vst[c] = st[vf];
            vf++;
            st[vf] = c;
        }
        vf = 0;
        st[0] = m + 1;
        nrj[l][m + 1] = -1;
        for (c = m; c > 0; c--) {
            while (nrj[l][c] <= nrj[l][st[vf]]) {
                vf--;
            }
            vdr[c] = st[vf];
            vf++;
            st[vf] = c;
        }
        for (c = 1; c <= m; c++) {
            maxsl[l] = maxim(maxsl[l], (vdr[c] - vst[c] - 1) * nrj[l][c]);
        }
    }
    for (l = n - 1; l > 0; l--) {
        maxsl[l] = maxim(maxsl[l], maxsl[l + 1]);
    }


    for (c = 1; c <= m; c++) {
        vf = 0;
        st[0] = 0;
        nrst[0][c] = -1;
        for (l = 1; l <= n; l++) {
            while (nrst[l][c] <= nrst[st[vf]][c]) {
                vf--;
            }
            vst[l] = st[vf];
            vf++;
            st[vf] = l;
        }
        vf = 0;
        st[0] = n + 1;
        nrst[n + 1][c] = -1;
        for (l = n; l > 0; l--) {
            while (nrst[l][c] <= nrst[st[vf]][c]) {
                vf--;
            }
            vdr[l] = st[vf];
            vf++;
            st[vf] = l;
        }
        for (l = 1; l <= n; l++) {
            maxpc[c] = maxim(maxpc[c], (vdr[l] - vst[l] - 1) * nrst[l][c]);
        }
        maxpc[c] = maxim(maxpc[c], maxpc[c - 1]);



        vf = 0;
        st[0] = 0;
        nrdr[0][c] = -1;
        for (l = 1; l <= n; l++) {
            while (nrdr[l][c] <= nrdr[st[vf]][c]) {
                vf--;
            }
            vst[l] = st[vf];
            vf++;
            st[vf] = l;
        }
        vf = 0;
        st[0] = n + 1;
        nrdr[n + 1][c] = -1;
        for (l = n; l > 0; l--) {
            while (nrdr[l][c] <= nrdr[st[vf]][c]) {
                vf--;
            }
            vdr[l] = st[vf];
            vf++;
            st[vf] = l;
        }
        for (l = 1; l <= n; l++) {
            maxsc[c] = maxim(maxsc[c], (vdr[l] - vst[l] - 1) * nrdr[l][c]);
        }
    }
    for (c = m - 1; c > 0; c--) {
        maxsc[c] = maxim(maxsc[c], maxsc[c + 1]);
    }
    rez = 0;
    for (l = 0; l <= n; l++) {
        if (maxpl[l] + maxsl[l + 1] > rez) {
            rez = maxpl[l] + maxsl[l + 1];
        }
    }
    for (c = 0; c <= m; c++) {
        if (maxpc[c] + maxsc[c + 1] > rez) {
            rez = maxpc[c] + maxsc[c + 1];
        }
    }
    fout = fopen("bmatrix.out", "w");
    fprintf(fout, "%d\n", rez);
    fclose(fout);
    return 0;
}