Cod sursa(job #2739964)

Utilizator AndreiAlexandru2k3Ciucan Andrei Alexandru AndreiAlexandru2k3 Data 10 aprilie 2021 18:44:15
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;

const int NMAX = 202;

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

char s[NMAX + 1];
int N, M,
    DP[NMAX][NMAX], A[NMAX][NMAX],
    up[NMAX], down[NMAX],
    leftt[NMAX], rightt[NMAX];

void read()
{
    f >> N >> M;
    for(int i = 1; i <= N; i++)
    {
        f >> s + 1;
        for(int j = 1; j <= M; j++)
            A[i][j] = s[j] - '0';
    }
}

void creare_DP_in_jos()
{
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            DP[i][j] = (A[i][j] == 0 ? DP[i - 1][j] + 1 : 0);
}

void creare_DP_in_sus()
{
    for(int i = 1; i <= M; i++)
        DP[N + 1][i] = 0;
    for(int i = N; i >= 1; i--)
        for(int j = 1; j <= M; j++)
            DP[i][j] = (A[i][j] == 0 ? DP[i + 1][j] + 1 : 0);
}

int arie(int l)
{
    stack<int>S;
    for (int i = 1; i <= M; ++i)
    {
        while (S.size() > 0 && DP[l][i] <= DP[l][S.top()])
            S.pop();
        leftt[i] = S.size() == 0 ? 1 : S.top() + 1;
        S.push(i);
    }
    while (S.size() > 0) S.pop();
    for (int i = M; i >= 1; --i)
    {
        while (S.size() > 0 && DP[l][i] <= DP[l][S.top()])
            S.pop();
        rightt[i] = S.size() == 0 ? M : S.top() - 1;
        S.push(i);
    }
    int area_max = 0;
    for(int i = 1; i <= M; i++)
    {
        int area = DP[l][i] * (rightt[i] - leftt[i] + 1);
        if(area > area_max)
            area_max = area;
    }
    return area_max;
}

void dp_up()
{
    for(int i = 1; i <= N; i++)
        up[i] = arie(i);
}

void dp_down()
{
    for(int i = N; i >= 1; i--)
        down[i] = arie(i);
}

int answer_Ox()
{
    for(int i = 2; i <= N; i++)
        if(up[i - 1] > up[i])
            up[i] = up[i - 1];
    //
    for(int i = N - 1; i >= 1; i--)
        if(down[i + 1] > down[i])
            down[i] = down[i + 1];
    //
    int maxx_2_areas=-1;
    down[N+1]=0;
    for(int i=1;i<=N;i++)
    {
        int area=up[i]+down[i+1];
        if(area>maxx_2_areas)
            maxx_2_areas=area;
    }
    return maxx_2_areas;
}

void swap(int &a, int &b)
{
    a = a ^ b;
    b = b ^ a;
    a = a ^ b;
}

void Rotate()
{
    static int B[NMAX][NMAX];
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            B[M - j + 1][i] = A[i][j];
    swap(N, M);
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            A[i][j] = B[i][j];

}

void solve()
{
    creare_DP_in_jos();
    dp_up();
    creare_DP_in_sus();
    dp_down();
}

int main()
{
    read();
    //
    solve();
    int rasp1 = answer_Ox();
    Rotate();
    solve();
    int rasp2 = answer_Ox(); ///de fapt Oy
    //
    g << max(rasp1, rasp2);
    return 0;
}