Cod sursa(job #2739945)

Utilizator AndreiAlexandru2k3Ciucan Andrei Alexandru AndreiAlexandru2k3 Data 10 aprilie 2021 17:02:36
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
///Brute Force
#include <iostream>
#include <fstream>
using namespace std;

const int NMAX = 201;

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];

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 afis_mat(int mat[][NMAX], int n, int m)
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            cout << mat[i][j] << ' ';
        cout << '\n';
    }
}

void afis_vectori()
{
    for(int i = 1; i <= N; i++)
        cout << up[i] << ' ';
    cout << '\n';
    for(int i = 1; i <= N; i++)
        cout << down[i] << ' ';
}

void creare_DP()
{
    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 arie(int l)
{
    for(int i = l; i <= N; i++)
    {
        int nr = 0, nrmax = -1;
        for(int j = 1; j <= M; j++)
            if(DP[i][j] >=  i - l + 1)
            {
                nr++;
                if(nr > nrmax)
                    nrmax = nr;
            }
            else nr = 0;
        int aria = nrmax * (i - l + 1);
        down[l] = max(aria, down[l]);
        up[i] = max(aria, up[i]);
    }
}

void dp()
{
    for(int i = 1; i <= N; i++)
        arie(i);
}

int answer_Ox()
{
    int arie_2_dreptunghiuri = max(down[1], up[N]), arie_2_dreptunghiuri_maxx = -1;
    for(int i = 1; i < N; i++)
        for(int j = i + 1; j <= N; j++)
        {
            arie_2_dreptunghiuri = up[i] + down[j];
            if(arie_2_dreptunghiuri > arie_2_dreptunghiuri_maxx)
                arie_2_dreptunghiuri_maxx = arie_2_dreptunghiuri;
        }
    return arie_2_dreptunghiuri_maxx;
}

void init()
{
    for(int i = 1; i <= N; i++)
        up[i]=down[i]=0;
}

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];

}

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