Pagini recente » Cod sursa (job #1863011) | Cod sursa (job #2806534) | Cod sursa (job #1892909) | Cod sursa (job #1806547) | Cod sursa (job #3229633)
#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;
}