Cod sursa(job #777359)

Utilizator vendettaSalajan Razvan vendetta Data 12 august 2012 01:32:41
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.92 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

#define nmax 202

int n, m, a[nmax][nmax], h[nmax][nmax], A[nmax], B[nmax], st[nmax], dr[nmax], sus[nmax], jos[nmax];
deque<int> dq;

void citeste(){

    f >> n >> m;
    f.get();
    for(int i=1; i<=n; i++){
        string s;
        getline(f,s);
        for(int j=0; j<m; j++) a[i][j+1] = (s[j] - '0');
    }

}

void extindere_st(int linie){

    dq.clear();
    dq.push_back(0);
    for(int j=1; j<=m; j++){
        while(dq.size() && h[linie][ dq.back() ] >= h[linie][j] ) dq.pop_back();
        if (dq.size() )st[j] = j-dq.back();//cat de mult ma pot duce in stanga avand un dreptunghi cu inaltimea h[i][j]
                else st[j] = 0;
        dq.push_back(j);
    }

}

void extindere_dr(int linie){

    dq.clear();
    dq.push_back(m+1);
    for(int j=m; j>=1; j--){
        while(dq.size() && h[linie][ dq.back() ] >= h[linie][j] )dq.pop_back();
        if (dq.size() )dr[j] = dq.back() - j;
                  else dr[j] = 0;
        dq.push_back(j);
    }

}

void extindere_sus_2(int coloana){

    dq.clear();
    dq.push_back(0);
    for(int i=1; i<=n; i++){
        while(dq.size() && h[ dq.back() ][coloana] >= h[i][coloana]) dq.pop_back();
        if (dq.size() ) sus[i] = i-dq.back();
                    else sus[i] = 0;
        dq.push_back(i);
    }

}

void extindere_jos_2(int coloana){

    dq.clear();
    dq.push_back(n+1);
    for(int i=n; i>=1; i--){
        while(dq.size() && h[ dq.back() ][coloana] >= h[i][coloana]) dq.pop_back();
        if( dq.size() ) jos[i] = dq.back() - i;
                    else jos[i] = 0;
        dq.push_back(i);
    }

}

void rezolva(){

    //trebuie sa determin 2 dreptunghiuri pline cu 0 care sa ocupe o arie maxima (iar aceste dreptunghiuri sa nu se suprapuna)
    //o(n^3) iau fiecare linie(si coloana) si presupun ca un dreptunghi se afla dreasupra linie si celalalt dedesubt;
            // aflu in n^2 drepuntghiul de arie maxima

    //o(n^2) : precalculez pentru fiecare linie cel mai mare dreptunghi care se afla pana pe acea linie (inclusiv) vin de sus in jos
                                    // cel mai mare drepuntghi care se afla pana pe acea linie(fara ea) vin jos in sus

    //ma duc de sus in jos
    //h[i][j] = cat de mult ma pot duce in sus eu fiind in (i,j)
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if (a[i][j] == 0) h[i][j] = h[i-1][j] + 1;
                         else h[i][j] = 0;
        }

        extindere_st(i);
        extindere_dr(i);

        A[i] = A[i-1];
        for(int j=1; j<=m; j++){
            int X = (st[j] + dr[j] - 1) * h[i][j];
            A[i] = max(A[i], X);
            //cout << dr[j] << " ";
        }
        //cout << A[i] << "\n";
        //cout << "\n";
    }

    //vin de jos in sus

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) h[i][j] = 0;

    for(int i=n; i>=1; i--){
        for(int j=1; j<=m; j++){
            if (a[i][j] == 0) h[i][j] = h[i+1][j] + 1;
                        else h[i][j] = 0;
        }

        extindere_st(i);
        extindere_dr(i);

        B[i] = B[i+1];
        for(int j=1; j<=m; j++){
            int X = (st[j] + dr[j] - 1 ) * h[i][j];
            B[i] = max(B[i], X);
        }
    }

    //iau fiecare linie si presuspun ca primul e deasupra incepand cu linia si celalalt dedesubt (fara linie)

    int rez = 0;

    for(int i=0; i<=n; i++){
        if (rez < A[i] + B[i+1]) rez = A[i] + B[i+1];
    }

    //acum iau fiecare coloana

    //vin de la stanga la dreapta
    //ca sa fie mai usor rastorn drepuntghiul => inaltimea in noul drepuntghi sa o fie defapt cat ma pot duce la stanga eu fiind in (i,j)...etc
    for(int j=1; j<=m; j++){
        for(int i=1; i<=n; i++){
            if (a[i][j] == 0) h[i][j] = h[i][j-1]+1;
                    else h[i][j] = 0;
        }

        extindere_sus_2(j);
        extindere_jos_2(j);

        A[j] = A[j-1];
        for(int i=1; i<=n; i++){
            int X = (sus[i] + jos[i] - 1) *h[i][j];
            A[j] = max(A[j], X);
            //cout << h[i][j] << " ";
        }
        //cout << "\n";
        //cout << A[j] << "\n";
    }

    //vin de la dreapta la stanga
    for(int j=m; j>=1; j--){
        for(int i=1; i<=n; i++){
            if (a[i][j] == 0) h[i][j] = h[i][j+1] + 1;
                        else h[i][j] = 0;
        }

        extindere_sus_2(j);
        extindere_jos_2(j);

        B[j] = B[j+1];
        for(int i=1; i<=n; i++){
            int X = (sus[i] + jos[i] - 1) * h[i][j];
            B[j] = max(B[j], X);
        }
    }

    //iau fiecare coloana
    for(int j=0; j<=m; j++){
        rez = max(rez, A[j] + B[j+1]);
    }

    g << rez << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}