Cod sursa(job #1730952)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 17 iulie 2016 21:44:29
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.68 kb
#include <fstream>
#include <math.h>

using namespace std;

string problemName = "bmatrix";
string inFile = problemName+".in";
string outFile = problemName+".out";
ifstream fin(inFile.c_str());
ofstream fout(outFile.c_str());

int rows, columns, answer;
const int Nmax = 205;
bool v[Nmax][Nmax];
int maximumHeight[Nmax][Nmax], maximumDepth[Nmax][Nmax];
int firstSmallerLeft[Nmax][Nmax], firstSmallerRight[Nmax][Nmax];
int bestRectangleAbove[Nmax], bestRectangleBelow[Nmax];
int stack[Nmax];

void read(){
    fin>>rows>>columns;
    string s;
    int i, j;
    for(i = 1;i <= rows;i++){
        fin>>s;
        for(j = 0;j < columns;j++){
            v[i][j+1] = s[j] - '0';
        }
    }
}

void print(){
    fout<<answer;
}

void printArray(int aux[][Nmax]){
    int i, j;
    for(i = 1;i <= rows;i++){
        for(j = 1;j <= columns;j++){
            fout<<aux[i][j]<<' ';
        }
        fout<<'\n';
    }
}

void getMaximumHeight(){
    int i, j;
    for(i = 1;i <= rows;i++){
        for(j = 1;j <= columns;j++){
            if(v[i][j] == 0){
                maximumHeight[i][j] = 1 + maximumHeight[i-1][j];
            }else{
                maximumHeight[i][j] = 0;
            }
        }
    }
}

void getFirstSmallerHeightLeft(){
    int i, j, last;
    for(i = 1;i <= rows;i++){
        last = 0;
        for(j = 1;j <= columns;j++){
            while(last > 0 && maximumHeight[i][j] <= maximumHeight[i][stack[last]]){
                last--;
            }
            if(last == 0){
                firstSmallerLeft[i][j] = 0;
            }else{
                firstSmallerLeft[i][j] = stack[last];
            }
            stack[++last] = j;
        }
    }
}

void getFirstSmallerHeightRight(){
    int i, j, last;
    for(i = 1;i <= rows;i++){
        last = 0;
        for(j = columns;j >= 1;j--){
            while(last > 0 && maximumHeight[i][j] <= maximumHeight[i][stack[last]]){
                last--;
            }
            if(last == 0){
                firstSmallerRight[i][j] = columns+1;
            }else{
                firstSmallerRight[i][j] = stack[last];
            }
            stack[++last] = j;
        }
    }
}

void getBestRectangleAbove(){
    int i, j;
    for(i = 1;i <= rows;i++){
        for(j = 1;j <= columns;j++){
            bestRectangleAbove[i] = max(bestRectangleAbove[i], maximumHeight[i][j] * (firstSmallerRight[i][j] - firstSmallerLeft[i][j] - 1));
        }
    }
    for(i = 1;i <= rows;i++){
        bestRectangleAbove[i] = max(bestRectangleAbove[i], bestRectangleAbove[i-1]);
    }
}

void solveAbove(){
    getMaximumHeight();
    getFirstSmallerHeightLeft();
    getFirstSmallerHeightRight();
    getBestRectangleAbove();
}

void getMaximumDepth(){
    int i, j;
    for(i = rows;i >= 1;i--){
        for(j = 1;j <= columns;j++){
            if(v[i][j] == 0){
                maximumDepth[i][j] = 1 + maximumDepth[i+1][j];
            }else{
                maximumDepth[i][j] = 0;
            }
        }
    }
}

void getFirstSmallerDepthLeft(){
    int i, j, last;
    for(i = 1;i <= rows;i++){
        last = 0;
        for(j = 1;j <= columns;j++){
            while(last > 0 && maximumDepth[i][j] <= maximumDepth[i][stack[last]]){
                last--;
            }
            if(last == 0){
                firstSmallerLeft[i][j] = 0;
            }else{
                firstSmallerLeft[i][j] = stack[last];
            }
            stack[++last] = j;
        }
    }
}

void getFirstSmallerDepthRight(){
    int i, j, last;
    for(i = 1;i <= rows;i++){
        last = 0;
        for(j = columns;j >= 1;j--){
            while(last > 0 && maximumDepth[i][j] <= maximumDepth[i][stack[last]]){
                last--;
            }
            if(last == 0){
                firstSmallerRight[i][j] = columns+1;
            }else{
                firstSmallerRight[i][j] = stack[last];
            }
            stack[++last] = j;
        }
    }
}

void getBestRectangleBelow(){
    int i, j;
    for(i = 1;i <= rows;i++){
        for(j = 1;j <= columns;j++){
            bestRectangleBelow[i] = max(bestRectangleBelow[i], maximumDepth[i][j] * (firstSmallerRight[i][j] - firstSmallerLeft[i][j] - 1));
        }
    }
    for(i = rows;i >= 1;i--){
        bestRectangleBelow[i] = max(bestRectangleBelow[i], bestRectangleBelow[i+1]);
    }
}

int mergeRectangles(){
    int i, currentBest = 0;
    for(i = 1;i < rows;i++){
        currentBest = max(currentBest, bestRectangleAbove[i]+bestRectangleBelow[i+1]);
    }
    return currentBest;
}

void solveBelow(){
    getMaximumDepth();
    getFirstSmallerDepthLeft();
    getFirstSmallerDepthRight();
    getBestRectangleBelow();
}

void solve(){
    solveAbove();
    solveBelow();
    answer = max(answer, mergeRectangles());
}

void rotateArray(){
    int i, j;
    bool aux[Nmax][Nmax];
    for(i = 1;i <= columns;i++){
        for(j = 1;j <= rows;j++){
            aux[i][j] = v[j][columns-i+1];
        }
    }
    for(i = 1;i <= columns;i++){
        for(j = 1;j <= rows;j++){
            v[i][j] = aux[i][j];
        }
    }
    swap(rows, columns);
}

void resetAll(){
    int i, j;
    for(i = 1;i <= rows;i++){
        for(j = 1;j <= columns;j++){
            maximumHeight[i][j] = 0;
            maximumDepth[i][j] = 0;
            firstSmallerLeft[i][j] = 0;
            firstSmallerRight[i][j] = 0;
        }
        bestRectangleAbove[i] = 0;
        bestRectangleBelow[i] = 0;
    }
}

void init(){
    read();
    solve();
    resetAll();
    rotateArray();
    solve();
    print();
}

int main(){
    init();
    return 0;
}