Cod sursa(job #2775957)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 18 septembrie 2021 12:19:11
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.56 kb
#include <fstream>
#include <stdio.h>
#include <string.h>
#include <stack>
#define NMAX 205

using namespace std;

/**********************************/
/// INPUT / OUTPUT

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
/**********************************/
/// GLOBAL DECLARATIONS

int N, M, res;
int tower[NMAX];
int ans[NMAX];
char mat[NMAX][NMAX]; // 1 - up, 2 - right, 3 - down, 4 - left
char temp[NMAX][NMAX];
int up[NMAX], l[NMAX], down[NMAX], r[NMAX];
/**********************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/**********************************/
///-----------------------------------------------
inline void ReadInput()
{
    f >> N >> M;

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            f >> mat[i][j];
}
///-----------------------------------------------
void RotateMat()
{
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            temp[j][N - i + 1] = mat[i][j];
    swap(N, M);

    // for (int i = 1 ; i <= N ; ++ i)
    //     for (int j = 1 ; j <= M ; ++ j)
    //         mat[i][j] = temp[i][j];
    memcpy(mat, temp, sizeof(mat));
}
///-----------------------------------------------
inline void PrintMat()
{
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
            g << mat[i][j];
        g << "\n";
    }
    g << "\n";
}
///-----------------------------------------------
void GetArray(int rot)
{
    memset(ans, 0, sizeof(ans));
    memset(tower, 0, sizeof(tower));

    stack<int> s;

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (mat[i][j + 1] == '0')
                tower[j]++;
            else
                tower[j] = 0;

            if (s.empty() || tower[s.top()] <= tower[j])
            {
                s.push(j);
                continue;
            }

            while (!s.empty() && tower[s.top()] > tower[j])
            {
                int top = s.top();
                s.pop();

                if (s.empty())
                    ans[i] = max(ans[i], tower[top] * j);
                else
                    ans[i] = max(ans[i], tower[top] * (j - s.top() - 1));
            }
            s.push(j);
        }
        while (!s.empty())
        {
            int top = s.top();
            s.pop();

            if (s.empty())
                ans[i] = max(ans[i], tower[top] * M);
            else
                ans[i] = max(ans[i], tower[top] * (M - s.top() - 1));
        }

        ans[i] = max(ans[i], ans[i - 1]);
    }

    switch (rot)
    {
    case 1:
        memcpy(up, ans, sizeof(up));
        break;
    case 2:
        memcpy(l, ans, sizeof(l));
        break;
    case 3:
        memcpy(down, ans, sizeof(down));
        break;
    case 4:
        memcpy(r, ans, sizeof(r));
        break;
    default:
        break;
    }
}
///-----------------------------------------------
inline void Solution()
{
    // PrintMat();
    GetArray(1);
    RotateMat();
    // PrintMat();
    GetArray(2);
    RotateMat();
    // PrintMat();
    GetArray(3);
    RotateMat();
    // PrintMat();
    GetArray(4);
    RotateMat();
    // PrintMat();

    for (int i = 1 ; i <= N ; ++ i)
    {
        g << up[i] << " " << down[N - i] << "\n";
        res = max(res, up[i] + down[N - i]);
    }
    
    for (int j = 1 ; j <= M ; ++ j)
    {
        res = max(res, l[j] + r[M - j]);
    }
}
///-----------------------------------------------
inline void Output()
{
    g << res;
}
///-----------------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}