Cod sursa(job #3276669)

Utilizator mateilucaLuca Matei Gabriel mateiluca Data 14 februarie 2025 08:30:56
Problema BMatrix Scor 96
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n, m, a[205][205], sp[205][205], sol, c[205], c2[205];
int st[205], top, stg[205], drp[205];
int st2[205], top2, stg2[205], drp2[205];
char ch[205];
pair<int, int> ss, dj;
void Verifica(int maxi)
{
    int i, j, maxim = 0, x, arie;
    for(i = ss.first;i <= dj.first;i++)
        for(j = ss.second;j <= dj.second;j++)
            a[i][j] = 1;
    for(j = 1;j <= m;j++)
        c2[j] = 0;
    for(i = 1;i <= n;i++)
    {
        for(j = 1;j <= m;j++)
            if(a[i][j] == 0) c2[j]++;
        else c2[j] = 0;
        top2 = 0;st2[0] = 0;
        for(j = 1;j <= m;j++)
        {
            x = c2[j];
            while(top2 > 0 && c2[j] <= c2[st2[top2]])
                top2--;
            stg2[j] = st2[top2];
            st2[++top2] = j;
        }
        top2 = 0;st2[0] = m + 1;
        for(j = m;j >= 1;j--)
        {
            x = c2[j];
            while(top2 > 0 && c2[j] <= c2[st2[top2]])
                top2--;
            drp2[j] = st2[top2];
            st2[++top2] = j;
        }
        for(j = 1;j <= m;j++)
        {
            arie = c2[j] * (drp2[j] - stg2[j] - 1);
            if(arie > maxim)
                maxim = arie;
        }
    }
    sol = max(sol, maxi + maxim);
    for(i = ss.first;i <= dj.first;i++)
        for(j = ss.second;j <= dj.second;j++)
            a[i][j] = 0;
}

int main()
{
    int i, j, x, l1, l2, maxi, arie;
    fin >> n >> m;
    fin.get();
    for(i = 1;i <= n;i++)
    {
        fin >> ch;
        for(j = 1;j <= m;j++)
            a[i][j] = ch[j - 1] - '0';
    }
    for(i = 1;i <= n;i++)
    {
        maxi = 0;
        for(j = 1;j <= m;j++)
            if(a[i][j] == 0) c[j]++;
        else c[j] = 0;
        top = 0;
        for(j = 1;j <= m;j++)
        {
            x = c[j];
            while(top > 0 && c[j] <= c[st[top]])
                top--;
            stg[j] = st[top];
            st[++top] = j;
        }
        top = 0;st[0] = m + 1;
        for(j = m;j >= 1;j--)
        {
            x = c[j];
            while(top > 0 && c[j] <= c[st[top]])
                top--;
            drp[j] = st[top];
            st[++top] = j;
        }
        for(j = 1;j <= m;j++)
        {
            arie = c[j] * (drp[j] - stg[j] - 1);
            if(arie > maxi)
            {
                maxi = arie;
                ss = {i - c[j] + 1, stg[j] + 1};
                dj = {i, drp[j] - 1};
            }
        }
        Verifica(maxi);
    }
    fout << sol << "\n";
    fout.close();
    return 0;
}