Cod sursa(job #3229633)

Utilizator Alex_BerbescuBerbescu Alexandru Alex_Berbescu Data 16 mai 2024 21:34:26
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.15 kb
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int dim = 2e2 + 5;
int n, m;
bool mat[dim][dim];
int splin[dim][dim], spcol[dim][dim], dp[dim][dim], maxi, maxidoi, pozlin[dim], pozcol[dim], dimlin, pozmaxilin, pozmaxilindoi;
vector<pair<pair<int, int>, int> >linii[dim];
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int32_t main(int argc, char * argv[])
{
    /*
    fac dreptunghiul intre liniile i si j imi trebuie sp pe linii si sp pe coloane


    **/
    fin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            fin >> mat[i][j];
            splin[i][j] = splin[i - 1][j] + 1;
            spcol[i][j] = spcol[i][j - 1] + 1;
            if(mat[i][j] == 1)
            {
                splin[i][j] = spcol[i][j] = 0;
            }
        }
    }
    int  stiva[dim] = {0}, dr[dim] = {0}, st[dim] = {0};
    for(int i = 1; i < n; ++i) // caut cel mai mare dreptunghi cu 0 intre liniile i si j
    {
        for(int j = i + 1; j <= n; ++j)
        {
            stiva[dim] = {0}, dr[dim] = {0}, st[dim] = {0};
            // height[t] = spcol[j][t] - spcol[i - 1][t];
            int dimu = 0;
            for(int k = 1; k <= m; ++k)
            {
                while(dimu && spcol[j][stiva[dimu]] - spcol[i - 1][stiva[dimu]] >= spcol[j][k] - spcol[i - 1][k])
                {
                    dimu--;
                }
                if(dimu == 0)
                {
                    st[k] = 0;
                }
                else
                {
                    st[k] = stiva[dimu];
                }
                stiva[++dimu] = k;
            }
            while(dimu)
            {
                stiva[--dimu] = 0;
            }
            for(int k = m; k >= 1; --k)
            {
                while(dimu && spcol[j][stiva[dimu]] - spcol[i - 1][stiva[dimu]] >= spcol[j][k] - spcol[i - 1][k])
                {
                    dimu--;
                }
                if(dimu == 0)
                {
                    dr[k] = m + 1;
                }
                else
                {
                    dr[k] = stiva[dimu];
                }
                stiva[++dimu] = k;
            }
            for(int k = 1; k <= m; ++k)
            {
                int arie = (dr[k] - st[k] - 1) * (spcol[j][k] - spcol[i - 1][k]);
                if(arie > maxi)
                {
                    maxi = arie;
                    pozmaxilin = i;
                    pozmaxilindoi = j;
                    pozlin[pozmaxilin] = i;
                    pozcol[pozmaxilin] = j;
                }
                linii[i].push_back({{st[k] + 1, dr[k] - 1}, j}); // bag coloanele in vectorul de linii
            }
        }
    }
    int ariemax = 0;
    for(auto it: linii[pozmaxilindoi + 1])
    {
        if(it.first.first >= pozlin[pozmaxilin] && it.first.second <= pozcol[pozmaxilin])
        {
            ariemax = max(ariemax, maxi + (it.first.second - it.first.first + 1) * (spcol[it.second][it.first.first] -  spcol[pozmaxilindoi][it.first.first]);
        }
    }
    fout << ariemax;
    return 0;


}