Cod sursa(job #1992987)

Utilizator Alex18maiAlex Enache Alex18mai Data 22 iunie 2017 02:12:27
Problema BMatrix Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.87 kb
#include <fstream>
#include <stack>

using namespace std;

ifstream cin ("bmatrix.in");
ofstream cout ("bmatrix.out");

char sir[205];
int A[205][205];
int aux[205][205];
int h[205][205];
int l[205][205];
int up[205];
int down[205];
int st[205];
int dr[205];
int oriz[205];
int vert[205];
stack <int> lft;
stack <int> rgt;

void intors (int m, int n){
    for (int i=1; i<=m; i++){
        for (int j=1; j<=n; j++){
            aux[n-j+1][i] = A[i][j];
        }
    }
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            A[i][j] = aux[i][j];
        }
    }
    return;
}

int main()
{
    int m, n;
    cin>>m>>n;
    for (int i=1; i<=m; i++){
        cin>>(sir+1);
        for (int j=1; j<=n; j++){
            A[i][j]=sir[j]-'0';
        }
    }
    for (int i=1; i<=m; i++){
        for (int j=1; j<=n; j++){
            if (A[i][j] == 0){
                h[i][j] = h[i-1][j] + 1;
            }
            if (A[i][j] == 1) {
                h[i][j] = 0;
            }
        }
    }
    for (int i=m; i>=1; i--){
        for (int j=1; j<=n; j++){
            if (A[i][j] == 0){
                l[i][j] = l[i+1][j] + 1;
            }
            else {
                l[i][j] = 0;
            }
        }
    }
    for (int k=1; k<=m; k++){
        while (!lft.empty()){
            lft.pop();
        }
        while (!rgt.empty()){
            rgt.pop();
        }
        lft.push(0);
        rgt.push(n+1);
        for (int j=1; j<=n; j++){
            while (h[k][j] <= h[k][lft.top()] && lft.size()>1){
                lft.pop();
            }
            st[j]=lft.top();
            lft.push(j);
        }
        for (int j=n; j>=1; j--){
            while (h[k][j] <= h[k][rgt.top()] && rgt.size()>1){
                rgt.pop();
            }
            dr[j]=rgt.top();
            rgt.push(j);
        }
        for (int j=1; j<=n; j++){
            up[j]=max(up[j-1], h[k][j] * (dr[j] - st[j] -1));
        }
        //up done
        while (!lft.empty()){
            lft.pop();
        }
        while (!rgt.empty()){
            rgt.pop();
        }
        lft.push(0);
        rgt.push(n+1);
        for (int j=1; j<=n; j++){
            while (l[k+1][j] <= l[k+1][lft.top()] && lft.size()>1){
                lft.pop();
            }
            st[j]=lft.top();
            lft.push(j);
        }
        for (int j=n; j>=1; j--){
            while (l[k+1][j] <= l[k+1][rgt.top()] && rgt.size()>1){
                rgt.pop();
            }
            dr[j]=rgt.top();
            rgt.push(j);
        }
        for (int j=1; j<=n; j++){
            down[j]=max(down[j-1], l[k+1][j] * (dr[j] - st[j] -1));
        }
        //down done
        oriz[k]=max(oriz[k-1], up[n] + down[n]);
    }
    intors(m,n);
    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;
            }
            if (A[i][j] == 1) {
                h[i][j] = 0;
            }
        }
    }
    for (int i=n; i>=1; i--){
        for (int j=1; j<=m; j++){
            if (A[i][j] == 0){
                l[i][j] = l[i+1][j] + 1;
            }
            else {
                l[i][j] = 0;
            }
        }
    }
    for (int k=1; k<=n; k++){
        while (!lft.empty()){
            lft.pop();
        }
        while (!rgt.empty()){
            rgt.pop();
        }
        lft.push(0);
        rgt.push(m+1);
        for (int j=1; j<=m; j++){
            while (h[k][j] <= h[k][lft.top()] && lft.size()>1){
                lft.pop();
            }
            st[j]=lft.top();
            lft.push(j);
        }
        for (int j=m; j>=1; j--){
            while (h[k][j] <= h[k][rgt.top()] && rgt.size()>1){
                rgt.pop();
            }
            dr[j]=rgt.top();
            rgt.push(j);
        }
        for (int j=1; j<=m; j++){
            up[j]=max(up[j-1], h[k][j] * (dr[j] - st[j] -1));
        }
        //up done
        while (!lft.empty()){
            lft.pop();
        }
        while (!rgt.empty()){
            rgt.pop();
        }
        lft.push(0);
        rgt.push(m+1);
        for (int j=1; j<=m; j++){
            while (l[k+1][j] <= l[k+1][lft.top()] && lft.size()>1){
                lft.pop();
            }
            st[j]=lft.top();
            lft.push(j);
        }
        for (int j=m; j>=1; j--){
            while (l[k+1][j] <= l[k+1][rgt.top()] && rgt.size()>1){
                rgt.pop();
            }
            dr[j]=rgt.top();
            rgt.push(j);
        }
        for (int j=1; j<=m; j++){
            down[j]=max(down[j-1], l[k+1][j] * (dr[j] - st[j] -1));
        }
        //down done
        vert[k]=max(vert[k-1], up[m] + down[m]);
    }
    cout<<max(oriz[m],vert[n])<<'\n';
    return 0;
}