#include "soccer.h"
using namespace std;
typedef vector<int> vi;
int biggest_stadium(int N, vector<vector<int>> F)
{
vector<vi> mn(N, vi(N)), mx(N, vi(N));
for(int c= 0; c < N; c++)
{
mn[0][c] = 0;
mx[N-1][c] = N-1;
}
for(int r = 1; r < N; r++)
{
for(int c= 0; c < N; c++)
{
if(F[r-1][c])
mn[r][c] = r;
else
mn[r][c] = mn[r-1][c];
int r2 = N-1-r;
if(F[r2+1][c])
mx[r2][c] = r2;
else
mx[r2][c] = mx[r2+1][c];
}
}
int out = 0;
for(int r = 0; r < N; r++)
{
for(int c= 0; c < N; c++)
{
vector<pair<int, int>> boundsl, boundsr;
int mx0 = mx[r][c], mn0 = mn[r][c];
int total = -(mx0-mn0+1);
for(int c2 = c; c2 >= 0 && !F[r][c2]; c2--)
{
mx0 = min(mx0, mx[r][c2]);
mn0 = max(mn0, mn[r][c2]);
boundsl.emplace_back(mx0, mn0);
}
mx0 = mx[r][c], mn0 = mn[r][c];
for(int c2 = c; c2 < N && !F[r][c2]; c2++)
{
mx0 = min(mx0, mx[r][c2]);
mn0 = max(mn0, mn[r][c2]);
boundsr.emplace_back(mx0, mn0);
}
while(!boundsl.empty() || !boundsr.empty())
{
if(boundsl.empty())
{
auto [t, b] = boundsr.back();
boundsr.pop_back();
total += t-b+1;
continue;
} else if (boundsr.empty()) {
auto [t, b] = boundsl.back();
boundsl.pop_back();
total += t-b+1;
continue;
}
auto [mx1, mn1] = boundsl.back();
auto [mx2, mn2] = boundsr.back();
if(mx1 >= mx2 && mn1 <= mn2)
{
auto [t, b] = boundsr.back();
boundsr.pop_back();
total += t-b+1;
} else if(mx2 >= mx1 && mn2 <= mn1) {
auto [t, b] = boundsl.back();
boundsl.pop_back();
total += t-b+1;
} else {
//piemel
int totl = 0, cutl = 0, totr = 0, cutr = 0;
while(!(boundsl.back().first >= mx2 && boundsl.back().second <= mn2))
{
auto [mx3, mn3] = boundsl.back();
boundsl.pop_back();
totl += mx3-mn3+1;
cutl += min(mx3, mx2) - max(mn3, mn2) + 1;
}
while(!(boundsr.back().first >= mx1 && boundsr.back().second <= mn1))
{
auto [mx3, mn3] = boundsr.back();
boundsr.pop_back();
totr += mx3-mn3+1;
cutr += min(mx3, mx1) - max(mn3, mn1) + 1;
}
total += max(totl + cutr, cutl + totr);
}
}
out = max(out, total);
}
}
return out;
}
