#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector <int>;
using vvi = vector <vi>;
using vll = vector <ll>;
int biggest_stadium (int n, vvi f) {
ll all = 0;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
all += f[i][j] == 0;
}
}
vvi ps(n+1, vi(n+1, 0));
for (ll i = 0; i < n; i++)
for (ll j = 0; j < n; j++)
ps[i+1][j+1] = !f[i][j];
for (ll i = 0; i <= n; i++) {
for (ll j = 1; j <= n; j++) {
ps[i][j] += ps[i][j-1];
}
}
for (ll i = 1; i <= n; i++) {
for (ll j = 0; j <= n; j++) {
ps[i][j] += ps[i-1][j];
}
}
auto query = [&](ll il, ll ir, ll jl, ll jr) { // [il, ir] and [jl, jr] 0-indexed
ir++; jr++;
return ps[ir][jr] - ps[ir][jl] - ps[il][jr] + ps[il][jl];
};
vvi nxtI(n, vi(n)), prvI(n, vi(n)), nxtJ(n, vi(n)), prvJ(n, vi(n));
for (ll j = 0; j < n; j++) prvI[0][j] = (f[0][j] ? 0 : -1);
for (ll i = 1; i < n; i++) {
for (ll j = 0; j < n; j++) {
prvI[i][j] = (f[i][j] ? i : prvI[i-1][j]);
}
}
for (ll i = 0; i < n; i++) prvJ[i][0] = (f[i][0] ? 0 : -1);
for (ll i = 0; i < n; i++) {
for (ll j = 1; j < n; j++) {
prvJ[i][j] = (f[i][j] ? j : prvJ[i][j-1]);
}
}
for (ll j = 0; j < n; j++) nxtI[n-1][j] = (f[n-1][j] ? n-1 : n);
for (ll i = n-2; i >= 0; i--) {
for (ll j = 0; j < n; j++) {
nxtI[i][j] = (f[i][j] ? i : nxtI[i+1][j]);
}
}
for (ll i = 0; i < n; i++) nxtJ[i][n-1] = (f[i][n-1] ? n-1 : n);
for (ll i = 0; i < n; i++) {
for (ll j = n-2; j >= 0; j--) {
nxtJ[i][j] = (f[i][j] ? j : nxtJ[i][j+1]);
}
}
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
if (f[i][j]) continue;
ll il = prvI[i][j], ir = nxtI[i][j];
ll jl = prvJ[i][j], jr = nxtJ[i][j];
ll cou = 0;
cou += query(0, il, 0, jl);
cou += query(ir, n-1, 0, jl);
cou += query(0, il, jr, n-1);
cou += query(ir, n-1, jr, n-1);
if (cou != 0) return 0;
}
}
for (ll i = 0; i < n; i++) {
ll j = 0;
for (; j < n; j++) if (!f[i][j]) break;
for (; j < n; j++) if (f[i][j]) break;
for (; j < n; j++) if (!f[i][j]) break;
if (j != n) return 0;
}
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < i; j++) {
swap(f[i][j], f[j][i]);
}
}
for (ll i = 0; i < n; i++) {
ll j = 0;
for (; j < n; j++) if (!f[i][j]) break;
for (; j < n; j++) if (f[i][j]) break;
for (; j < n; j++) if (!f[i][j]) break;
if (j != n) return 0;
}
return all;
}
