#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
int ret = 0;
int xx [] = {-1 , 1 , 0 , 0};
int yy[] = {0 , 0 , -1 , 1};
int gans = 0;
vector<pair<int ,int>> v;
vector<vector<int>> grid;
int MAXN = 0;
int get_nest(pair<int ,int> a , pair<int ,int> b)
{
if(a.first == b.first && a.second == b.second)
return 2;
if(a.first <= b.first && b.second <= a.second)
return 0;
swap(a , b);
if(a.first <= b.first && b.second <= a.second)
return 1;
return -1;
}
bool works()
{
int N = (int)v.size() - 1;
int lst0 = 0;
vector<int> type(N + 1);
for(int i = 2 ; i <= N ; i++)
{
if(v[i].first == -1 || v[i - 1].first == -1)
{
type[i] = 2;
continue;
}
if(v[i].first == v[i - 1].first && v[i].second == v[i - 1].second)
{
type[i] = 2;
continue;
}
type[i] = get_nest(v[i] , v[i - 1]);
if(type[i] == -1)
{
return 0;
}
if(type[i] == 0)
lst0 = i;
}
if(lst0 == 0)
{
return 1;
}
int nb1 = count(type.begin() + 2 , type.begin() + lst0+1 , 1);
if(nb1)
return 0;
vector<vector<int>>l(MAXN + 1);
for(int i = 1 ; i <= N ; i++)
{
if(v[i].first != -1)
{
l[v[i].first].push_back(v[i].second);
}
}
int mxR = 0;
for(int i = MAXN ; i >= 1 ; i--)
{
for(auto r : l[i])
{
if(mxR > r)
{
return 0;
}
}
for(auto r : l[i])
{
mxR = max(mxR , r);
}
}
return 1;
}
vector<vector<pair<int, int>>> intervals;
const int C = 5;
void get_intervals(int N)
{
for(int i = 1 ; i <= N ; i++)
{
for(int j = 1 ; j <= N ; )
{
int k = j;
for( ; j <= N && grid[i][j] == grid[i][k]; j++);
if(grid[i][k] == 0)
{
int lt = k , rt = j - 1;
int len = j - k;
for(int h = lt ; h <= rt ; h++)
{
for(int l = h ; l <= rt ; l++)
{
if(len - (l - h + 1) <= C)
intervals[i].push_back({h , l});
}
}
}
}
sort(intervals[i].rbegin() , intervals[i].rend() , [](pair<int ,int> a , pair<int, int> b){return a.second-a.first < b.second-b.first;});
}
}
int cur = 0;
void brute(int i)
{
if (1.0 * clock() / CLOCKS_PER_SEC >= 4.499)
return ;
if(i == MAXN + 1)
{
// cerr<<"cur : "<<cur<<'\n';
// cerr<<(int)v.size()<<'\n';
return ;
}
for(auto [l , r] : intervals[i])
{
if (1.0 * clock() / CLOCKS_PER_SEC >= 4.499)
return ;
// cerr<<i<<" "<<l<<" "<<r<<'\n';
v.push_back({l , r});
bool check = works();
if(check)
{
cur+= r - l + 1;
gans = max(gans , cur);
brute(i + 1);
cur-= (r - l + 1);
v.pop_back();
}
else
v.pop_back();
}
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
MAXN = N;
gans = 0;
v.clear();
grid.assign(N + 2 ,vector<int> (N + 2 , 1));
intervals.assign(N + 1 , vector<pair<int ,int>>());
for(int i= 1 ; i <= N ; i++)
{
for(int j = 1 ; j <= N ; j++)
{
grid[i][j] = F[i-1][j-1];
}
}
get_intervals(N);
for(int i = 1 ; i <= MAXN ; i++)
{
v.clear();
cur = 0;
v.push_back({-1 , -1});
brute(i );
}
assert(gans >= 1);
return gans;
}
/*
--
----
----
------
------
----
*/
