Cod sursa(job #1311224)

Utilizator mariusn01Marius Nicoli mariusn01 Data 7 ianuarie 2015 20:57:52
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.63 kb
#include <fstream>
#include <iostream>

#define DIM 203
using namespace std;

struct nod {
    int h;
    int p;
};

nod S[DIM];

char s[DIM][DIM], b[DIM][DIM];

int a[DIM][DIM];

int sus[DIM], jos[DIM];

int n, m, i, j, sol, nr;

void calcul() {
    int i, j, k, aria, poz, aux;


    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++)
            if (s[i][j] == '0')
                a[i][j] = 1 + a[i-1][j];
            else
                a[i][j] = 0;
        sus[i] = jos[i] = 0;
    }

    for (i=1;i<=n;i++) {
        k = 0;
        for (j=1;j<=m+1;j++){
            if (a[i][j] > S[k].h) {
                k++;
                S[k].h = a[i][j];
                S[k].p = j;
                continue;
            }
            while (k > 0 && a[i][j] <= S[k].h) {
                int aria = (j-S[k].p)*S[k].h;
                sus[i] = max(sus[i], aria);

                poz = S[k].p;
                k--;
            }
            if (a[i][j] > 0) {
                k++;
                S[k].p = poz;
                S[k].h = a[i][j];
            }
        }
    }

    for (i=2;i<=n;i++)
        sus[i] = max(sus[i], sus[i-1]);

    for (i=1;i<=n/2;i++)
        for (j=1;j<=m;j++) {
            aux = s[i][j];
            s[i][j] = s[n-i+1][j];
            s[n-i+1][j] = aux;
        }




    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++)
            if (s[i][j] == '0')
                a[i][j] = 1 + a[i-1][j];
            else
                a[i][j] = 0;

    }

    for (i=1;i<=n;i++) {
        k = 0;
        for (j=1;j<=m+1;j++){
            if (a[i][j] > S[k].h) {
                k++;
                S[k].h = a[i][j];
                S[k].p = j;
                continue;
            }
            while (k > 0 && a[i][j] <= S[k].h) {
                int aria = (j-S[k].p)*S[k].h;
                jos[i] = max(jos[i], aria);

                poz = S[k].p;
                k--;
            }
            if (a[i][j] > 0) {
                k++;
                S[k].p = poz;
                S[k].h = a[i][j];
            }
        }
    }

    for (i=2;i<=n;i++)
        jos[i] = max(jos[i], jos[i-1]);

    for (i=1;i<=n/2;i++) {
        aux = jos[i];
        jos[i] = jos[n-i+1];
        jos[n-i+1] = aux;
    }

    for (i=1;i<=n/2;i++)
        for (j=1;j<=m;j++) {
            aux = s[i][j];
            s[i][j] = s[n-i+1][j];
            s[n-i+1][j] = aux;
        }





/*
    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++) {
            nr = 0;
            for (k=1;k<=m;k++) {
                if (a[j][k] >= j-i+1)
                    nr++;
                else
                    nr=0;

                aria = nr * (j-i+1);
                sus[j] = max(sus[j], aria);
                jos[i] = max(jos[i], aria);
            }
        }
*/


}



void afisare(char a[DIM][DIM], int n, int m) {
    int i, j;
    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++)
            cout<<a[i][j];
        cout<<"\n";
    }
    cout<<"\n";

}


ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

int main() {
    fin>>n>>m;
    for (i=1;i<=n;i++) {
        fin>>s[i] + 1;
    }

    //afisare(s, n, m);

    calcul();
    for (i=1;i<n;i++)
        sol = max(sol, jos[i+1] + sus[i]);


    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            b[m-j+1][i] = s[i][j];

    swap(n, m);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            s[i][j] = b[i][j];

//  afisare(s, n, m);

    calcul();
    for (i=1;i<n;i++)
        sol = max(sol, jos[i+1] + sus[i]);

    fout<<sol;

    return 0;
}