#include "soccer.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0;i<n;i++)
#define FOR(i, k, n) for(int i = k;i<n;i++)
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define mp make_pair
#define vpii vector<pii>
#define vvi vector<vi>
using namespace std;
bool solve(pii a, pii b, vvi &psr, vvi &psc){
if(a.first == b.first || a.second == b.second){
return 1;
}
int s1 = psr[a.first][max(a.second, b.second) + 1] - psr[a.first][min(a.second, b.second)] +
psc[b.second][max(a.first, b.first) + 1] - psc[b.second][min(a.first, b.first)];
int s2 = psc[a.second][max(a.first, b.first) + 1] - psc[a.second][min(a.first, b.first)] +
psr[b.first][max(a.second, b.second) + 1] - psr[b.first][min(a.second, b.second)];
if(s1 == 0 || s2 == 0)return 1;
else return 0;
}
signed biggest_stadium(signed n, std::vector<std::vector<signed>> v)
{
int s = 0;
pii p = mp(-1,-1);
f0r(i,n){
f0r(j,n){
s += v[i][j];
if(v[i][j])p = mp(i,j);
}
}
if(s == 0){
return n * n;
}
else if(s == 1){
int a = min(p.first+1, n-p.first);
int b = min(p.second+1, n-p.second);
return n * n - a * b;
}
else if(n <= 3){
int ans = 0;
f0r(i, (1LL << (n * n))){
vector<vector<signed>>V(n, vector<signed>(n));
int sum = 0;
bool oke = 1;
f0r(j, n * n){
if((1LL << j) & i){
V[j/n][j%n] = 1;
}
else{
V[j/n][j%n] = 0; sum++;
if(v[j/n][j%n] == 1)oke = 0;
}
}
if(oke){
vector<vector<signed>>v = V;
bool ok = 1;
f0r(i,n){
bool off = 0;
f0r(j,n){
if(off){
if(v[i][j] == 0 && v[i][j-1] == 1){
ok = 0;
}
}
if(v[i][j] == 0){
off = 1;
}
}
}
f0r(j,n){
bool off = 0;
f0r(i,n){
if(off){
if(v[i][j] == 0 && v[i-1][j] == 1){
ok = 0;
}
}
if(v[i][j] == 0){
off = 1;
}
}
}
if(!ok){
continue;
}
else{
vpii pts;
vvi psr; //fix i move j
vvi psc; //fix j move i
f0r(i,n){
vi ps(n+1);
int la = -1;
f0r(j,n){
ps[j+1] = ps[j] + v[i][j];
if(v[i][j] == 0)la = j;
}
int fi = -1;
f0r(j,n){
if(v[i][j] == 0){
fi = j; break;
}
}
if(la != -1){
pts.pb(mp(i, la));
}
if(fi != -1 && fi != la){
pts.pb(mp(i, fi));
}
psr.pb(ps);
}
f0r(i,n){
vi ps(n+1);
int la = -1;
f0r(j,n){
ps[j+1] = ps[j] + v[j][i];
if(v[j][i] == 0)la = j;
}
int fi = -1;
f0r(j,n){
if(v[j][i] == 0){
fi = j; break;
}
}
if(la != -1){
pts.pb(mp(la, i));
}
if(fi != -1 && fi != la){
pts.pb(mp(fi, i));
}
psc.pb(ps);
}
f0r(i,pts.size()){
f0r(j,pts.size()){
if(i != j){
if(!solve(pts[i], pts[j], psr, psc)){
ok = 0;
}
}
}
}
if(ok){
ans = max(ans, sum);
}
}
}
}
return ans;
}
else{
bool ok = 1;
f0r(i,n){
bool off = 0;
f0r(j,n){
if(off){
if(v[i][j] == 0 && v[i][j-1] == 1){
ok = 0;
}
}
if(v[i][j] == 0){
off = 1;
}
}
}
f0r(j,n){
bool off = 0;
f0r(i,n){
if(off){
if(v[i][j] == 0 && v[i-1][j] == 1){
ok = 0;
}
}
if(v[i][j] == 0){
off = 1;
}
}
}
if(!ok){
return 0;
}
else{
vpii pts;
vvi psr; //fix i move j
vvi psc; //fix j move i
f0r(i,n){
vi ps(n+1);
int la = -1;
f0r(j,n){
ps[j+1] = ps[j] + v[i][j];
if(v[i][j] == 0)la = j;
}
int fi = -1;
f0r(j,n){
if(v[i][j] == 0){
fi = j; break;
}
}
if(la != -1){
pts.pb(mp(i, la));
}
if(fi != -1 && fi != la){
pts.pb(mp(i, fi));
}
psr.pb(ps);
}
f0r(i,n){
vi ps(n+1);
int la = -1;
f0r(j,n){
ps[j+1] = ps[j] + v[j][i];
if(v[j][i] == 0)la = j;
}
int fi = -1;
f0r(j,n){
if(v[j][i] == 0){
fi = j; break;
}
}
if(la != -1){
pts.pb(mp(la, i));
}
if(fi != -1 && fi != la){
pts.pb(mp(fi, i));
}
psc.pb(ps);
}
f0r(i,pts.size()){
f0r(j,pts.size()){
if(i != j){
if(!solve(pts[i], pts[j], psr, psc)){
ok = 0;
}
}
}
}
if(ok)return n*n-s;
else return 0;
}
}
return 0;
}
