Cod sursa(job #775157)

Utilizator vendettaSalajan Razvan vendetta Data 7 august 2012 14:02:36
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.38 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

#define nmax 202

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

void citeste(){

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

}

void rezolva(){

    //am nevoie de 2 dreptunghiuri care nu se suprapun si ocupa impreuna o arie cat mai mare;
    //pt a nu se suprapune aleg toate posibilitaile de a alege 2 dreptunghiuri : aleg o linie si presupun ca un dreptunghi sa fie dreasupra celelat dedesubt
    //aleg o coloana si presupun ca un dreptunghi sa fie la stanga / la dreapta acestei coloane

    //aflu dreptunghiul de arie maxima in m*n
    //preprocesez pentru fiecare i,j cate de mult ma pot duce in sus daca ma aflu in i,j
    //acum ma intereseaza cat de mult ma pot duce in stanga/si indreapta AVAND INALTIMEA DREPTUNGHIULUI LA FEL CA h[i][j];
    //e corect pt ca : apare cazul cand eu sunt in (i,j) si am inaltimea h[i][j]; si ma duc la stanga 1 pasi iar la dreapta 1 pas :
    //astfel se form un dreptunghi de h[i][j] * 3; dar daca alegeam o inaltime mai mica puteam sa formez un dreptunghi mai mare;
    //DAR acest dreptunghi oricum se va forma cand ajung la coloana respectiva;
    //deci ma duc in stanga si in dreapta atata timp cat coloane au o inaltime mai mare sau cel putin egale cu inaltimea mea

    //aleg o linie acum
    //primul dreptunghi se termina cel mult pe linia i iar al doilea incepe cel mult pe linia i+1

    int rez = 0;
    for(int linie = 1; linie<m; linie++){
        //primul dreptunghi
        int rez1 = 0;
        int rez2 = 0;

        for(int j=1; j<=n; j++) h[linie][j] = 0, st[j] = 0, dr[j] = 0;

        for(int i=1; i<=linie; i++){
            // aflu pentru fiecare cat de mult ma pot duce in sus
            for(int j=1; j<=n; j++){
                if (a[i][j] == 1){
                    h[i][j] = 0;
                    continue;
                }
                h[i][j] = h[i-1][j] + 1;
            }
            //acum aflu extinderea la dreapta si la stanga a elementului i,j
            //la dreapta(=> vin din dreapta)
            dq.clear();
            dq.push_back(n+1);
            h[i][n+1] = -1;//cazul cand o coloana poate merge pana in capat
            for(int j=n; j>=1; j--){
                //if (a[i][j] == 1) continue;
                while( dq.size() && h[i][j] <= h[i][dq.back()]) dq.pop_back();
                dr[j] = dq.back()-1;//asta imi da prima coloana mai mica strict ca si a mea =>
                //pana la aceasta coloana toate au fost mai mari sau cel putin egal cu mea
                dq.push_back(j);
            }

            // la stanga
            dq.clear();
            dq.push_back(0);
            h[i][0] = -1;
            for(int j=1; j<=n; j++){
                //if (a[i][j] == 1) continue;
                while(dq.size() && h[i][j] <= h[i][dq.back()] ) dq.pop_back();
                st[j] = dq.back()+1;
                dq.push_back(j);
            }
            //calculez pentru fiecare cooana dreptunghiul cu h = h[i][j]
            for(int j=1; j<=n; j++){
                if (a[i][j] == 1) continue;
                //if (linie == 2 && i == 2)cout << j << " " << st[j] << " " << dr[j] << "\n";
                int St = j-st[j]+1;//cate coloana sunt intre st[j] si j
                int Dr = dr[j]-j + 1;
                int Total = St + Dr-1; // -1 pt ca coloana j a fost pusa de 2 ori
                if (rez1 < h[i][j] * Total){
                    rez1 = h[i][j] * Total;
                }
            }
        }

        for(int j=1; j<=n; j++) h[linie][j] = 0, st[j] = 0, dr[j] = 0;

        for(int i=linie+1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if (a[i][j] == 1){
                    h[i][j] = 0;
                    //continue;
                }
                else h[i][j] = h[i-1][j] + 1;
            }
            dq.clear();
            h[i][n+1] = -1;
            dq.push_back(n+1);
            //la dreapta
            for(int j=n; j>=1; j--){
                //if (a[i][j] == 1) continue;
                while(dq.size() && h[i][j] <= h[i][dq.back()]) dq.pop_back();
                dr[j] = dq.back() -1;
                dq.push_back(j);
            }

            dq.clear();
            h[i][0] = -1;
            dq.push_back(0);
            //la stanga
            for(int j=1; j<=n; j++){
                //if (a[i][j] == 1) continue;
                while(dq.size() && h[i][j] <= h[i][dq.back()]) dq.pop_back();
                st[j] = dq.back() + 1;
                dq.push_back(j);
            }

            //total
            for(int j=1; j<=n; j++){
                if (a[i][j] == 1) continue;
                int St = j-st[j] + 1;
                int Dr = dr[j] - j +1;
                int Total = St + Dr - 1;
                if (rez2 < h[i][j] * Total){
                    rez2 = h[i][j] * Total;
                }
            }
        }
        if (rez < rez1 + rez2){
            rez = rez1 + rez2;
        }
    }

    g << rez << "\n";

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}