#include "soccer.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define big(x) ((int)(x.size()))
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
int ctr = 0;
pii pos;
for (int i=1;i<=N;i++) {
for (int j = 1;j<=N;j++) {
if (F[i-1][j-1] == 1) {
ctr++,pos = {i,j};
}
}
}
if (ctr == 1) {
int i = pos.ff,j = pos.ss;
int ans1 = (i-1)*N+(N-j)*(N-i+1);
int ans2 = (i-1)*N+(j-1)*(N-i+1);
int ans3 = (N-i)*N+(N-j)*(i);
int ans4 = (N-i)*N+(j-1)*(i);
return max({ans1,ans2,ans3,ans4});
}
vector<pii> maximal[N+1];
for (int j = 1;j<=N;j++) {
for (int i = 1;i<=N;) {
if (F[i-1][j-1] == 1) {
i++;
continue;
}
int cur = i;
while (cur < N && F[cur][j-1] == 0) cur++;
maximal[j].push_back({i,cur});
i = cur+1;
}
}
if (N <= 30) {
int dp[N+1][N+1][N+1][N+1];
memset(dp,0,sizeof dp);
int ans = 0;
for (int L = N;L>=1;L--) {
for (auto it : maximal[L]) {
int& dpp = dp[L][L][it.ff][it.ss];
dpp = max(dpp,it.ss-it.ff+1);
}
for (int R= L; R <= N;R++) {
for (int l = 1;l<=N;l++) {
for (int r = l;r <= N;r++) {
if (!dp[L][R][l][r]) continue;
ans = max(ans,dp[L][R][l][r]);
if (L>1) {
for (auto it : maximal[L-1]) {
int newl = max(l,it.ff),newr = min(r,it.ss);
if (newl > newr) continue;
int& dpp = dp[L-1][R][newl][newr];
dpp = max(dpp,dp[L][R][l][r]+newr-newl+1);
}
}
if (R < N) {
for (auto it : maximal[R+1]) {
int newl = max(l,it.ff),newr = min(r,it.ss);
if (newl > newr) continue;
int& dpp = dp[L][R+1][newl][newr];
dpp = max(dpp,dp[L][R][l][r]+newr-newl+1);
}
}
}
}
}
}
return ans;
}
for (int i=1;i<=N;i++) {
if (maximal[i].size() > 1) return 0;
}
bool dp[N+1][N+1];
memset(dp,0,sizeof dp);
for (int L = N;L>=1;L--) {
dp[L][L] = 1;
for (int R= L; R <= N;R++) {
int myl = max((big(maximal[L])?maximal[L][0].ff:(N+1)),(big(maximal[R])?maximal[R][0].ff:(N+1)));
int myr = min((big(maximal[L])?maximal[L][0].ss:0),(big(maximal[R])?maximal[R][0].ss:(0)));
if (L > 1) {
if (maximal[L-1].empty()) {
dp[L-1][R] = 1;
continue;
}
int hisl = maximal[L-1][0].ff;
int hisr = maximal[L-1][0].ss;
if (hisl >= myl && hisr >= myr) {
dp[L-1][R] = 1;
}
}
if (R < N) {
if (maximal[R+1].empty()) {
dp[L][R+1] = 1;
continue;
}
int hisl = maximal[R+1][0].ff;
int hisr = maximal[R+1][0].ss;
if (hisl >= myl && hisr >= myr) {
dp[L-1][R+1] = 1;
}
}
}
}
if (dp[1][N]) return N*N-ctr;
return 0;
}
