#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " ------> " << x << endl;
const int mxN = 2005;
ll n,a[mxN][mxN],p[mxN][mxN],L[2][mxN][mxN],R[2][mxN][mxN];
bool check(){
vector<vector<int>> mx(2, vector<int>(n + 5, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
L[0][i][j] = L[1][i][j] = R[0][i][j] = R[1][i][j] = 0;
if(a[i][j]){
mx[0][i] = j;
mx[1][j] = i;
}
p[i][j] = a[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(!a[i][j]) continue;
if(a[i][j - 1]) L[0][i][j] = L[0][i][j - 1];
else L[0][i][j] = j;
if(a[i - 1][j]) L[1][i][j] = L[1][i - 1][j];
else L[1][i][j] = i;
}
}
for(int i = n; i >= 1; i--){
for(int j = n; j >= 1; j--){
if(!a[i][j]) continue;
if(a[i][j + 1]) R[0][i][j] = R[0][i][j + 1];
else{
R[0][i][j] = j;
if(mx[0][i] > j) return 0;
}
if(a[i + 1][j]) R[1][i][j] = R[1][i + 1][j];
else{
R[1][i][j] = i;
if(mx[1][j] > i) return 0;
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(!a[i][j]) continue;
if(p[L[1][i][j] - 1][L[0][i][j] - 1]) return 0;
if(p[L[1][i][j] - 1][n] - p[L[1][i][j] - 1][R[0][i][j]]) return 0;
if(p[n][L[0][i][j] - 1] - p[R[1][i][j]][L[0][i][j] - 1]) return 0;
if(p[n][n] + p[R[1][i][j]][R[0][i][j]] - p[n][R[0][i][j]] - p[R[1][i][j]][n]) return 0;
}
}
return true;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F){
n = N;
int ans = 0;
for(int bit = 1; bit < (1 << (n * n)); bit++){
for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) a[i][j] = 0;
bool ok = true;
for(int i = 0; i < n * n; i++){
if((1 << i) & bit and F[i / n][i % n]){
ok = false;
break;
}
if((1 << i) & bit) a[i / n + 1][i % n + 1] = 1;
}
if(ok and check()) ans = max(ans, __builtin_popcount(bit));
}
return ans;
}
