Cod sursa(job #3268521)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 15 ianuarie 2025 18:51:54
Problema BMatrix Scor 28
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 202, M_MAX = 202;
int N, M;
int m[N_MAX][M_MAX]; // m[i][j] = 2 => avem un 0 deja folosit
int col[N_MAX][M_MAX];
int used[N_MAX][M_MAX]; // = suma partiala pe matrice pt nr de celule de 2
char s[M_MAX];

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadInput()
{
    cin >> N >> M;
    cin.getline(s, M_MAX);

    for(int i = 1, j; i <= N; i++)
    {
        cin.getline(s + 1, M_MAX);
        for(j = 1; j <= M; j++)
            m[i][j] = s[j] - '0';
    }
}

void Border()
{
    for(int i = 0; i <= N + 1; i++)
        m[i][0] = m[i][M+1] = 1;

    for(int j = 0; j <= M + 1; j++)
        m[0][j] = m[N+1][j] = 1;
}

inline int CalcUsed(int r1, int c1, int r2, int c2)
{
    if(used[r2][c2] == 0)
        return 0;
    return used[r2][c2] - used[r2][c1-1] - used[r1-1][c2] + used[r1-1][c2-1];
}

int FindMaxRecArea()
{
    int maxArea = 0;
    pair<int, int> recPos, recSize;
    stack<pair<int, int> > peaks; /// {lin[i][j], j} unde i este ramane constant

    for(int i = 1, j; i <= N; i++)
        for(j = 1; j <= M + 1; j++) /// j <= M + 1 pt ca m[i][M+1] = 1 pt orice i si se reseteaza stack-ul
        {
            used[i][j] = used[i-1][j] + used[i][j-1] - used[i-1][j-1] + (m[i][j] == 2);
            if(m[i][j] == 1)
                col[i][j] = 0;
            else
                col[i][j] = col[i-1][j] + 1;

            pair<int, int> top;
            int area;

            while(not peaks.empty() && peaks.top().first > col[i][j])
            {
                top = peaks.top();
                peaks.pop();

                area = top.first * (j - 1 - top.second + 1) - CalcUsed(i - top.first + 1, top.second, i, j - 1);

                if(area > maxArea)
                {
                    maxArea = area;
                    recPos = make_pair(i, j-1);
                    recSize = make_pair(j - top.second, top.first);
                }
            }

            if(col[i][j] != 0)
                peaks.push(make_pair(col[i][j], j));
        }

    for(int i = recPos.first - recSize.second + 1; i <= recPos.first; i++)
        for(int j = recPos.second - recSize.first + 1; j <= recPos.second; j++)
            m[i][j] = 2;

    return maxArea;
}

void Solve()
{
    int firstArea = FindMaxRecArea();
    int secondArea = FindMaxRecArea();

    cout << firstArea + secondArea;
}

int main()
{
    SetInput("bmatrix");
    ReadInput();
    Border();
    Solve();

    return 0;
}