Cod sursa(job #2929208)

Utilizator Theodor17Pirnog Theodor Ioan Theodor17 Data 25 octombrie 2022 11:10:23
Problema BMatrix Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <fstream>
#include <stack>

using namespace std;

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

const int NMAX = 2e2;

int n, m;
int dp[NMAX + 1][NMAX + 1], a[NMAX + 1][NMAX + 1], b[NMAX + 1][NMAX + 1], h[NMAX + 1], last[NMAX + 1], st[NMAX + 1], dr[NMAX + 1];

struct dreptunghi{

    int x1, y1, x2, y2;

};

void solve(int &amax, int lin, dreptunghi &d1, int a[][NMAX + 1]){

    stack <int> s, d;

    for(int i = 1; i <= n; i++){

        while(!s.empty() && h[i] <= h[s.top()])
            s.pop();

        if(s.empty())
            st[i] = 1;
        else st[i] = s.top() + 1;

        s.push(i);

    }

    for(int i = n; i >= 1; i--){

        while(!d.empty() && h[i] <= h[d.top()])
            d.pop();

        if(d.empty())
            dr[i] = n;
        else dr[i] = d.top() - 1;

        int arie = h[i] * (dr[i] - st[i] + 1);

        if(amax < arie){

            d1.x2 = lin;
            d1.y2 = dr[i];

            d1.x1 = lin - h[i] + 1;
            d1.y1 = st[i];

            amax = arie;

        }

        d.push(i);

    }

}

int main(){

    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){

            char ch;
            cin >> ch;

            a[i][j] = ch - 48;

        }
    }

    int amax = 0;
    dreptunghi d1;

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= m; j++){

            if(a[i][j] == 1)
                h[j] = 0;
            else h[j] = 1 + last[j];

            last[j] = h[j];

        }

        solve(amax, i, d1, a);

    }


    //cout << amax << " => (" << d1.x1 << ", " << d1.y1 << ") x (" << d1.x2 << ", " << d1.y2 << ")\n";

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){

            if(d1.x1 <= i && i <= d1.x2){

                if(j < d1.y1)
                    b[i][j] = a[i][j];
                else if(d1.y1 <= j && j <= d1.y2 && j + d1.y2 - d1.y1 + 1 <= m)
                    b[i][j] = a[i][j + d1.y2 - d1.y1 + 1];
                else b[i][j] = 1;

            }else
                b[i][j] = a[i][j];

        }
    }


    int amax2 = 0;
    dreptunghi d2;

    for(int i = 1; i <= m; i++)
        last[i] = 0;

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= m; j++){

            if(b[i][j] == 1)
                h[j] = 0;
            else h[j] = 1 + last[j];

            last[j] = h[j];

        }

        solve(amax2, i, d2, b);

    }

    //cout << amax2 << " => (" << d2.x1 << ", " << d2.y1 << ") x (" << d2.x2 << ", " << d2.y2 << ")\n";

    cout << amax + amax2;

    return 0;
}