#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<vector<int>> pref;
vector<vector<signed>> field;
int INF = 1LL<<30;
int query(int a, int b, int c, int d) {
if (a<c) swap(a,c);
if (b<d) swap(b,d);
return pref[c+1][d+1]-pref[a][d+1]-pref[c+1][b]+pref[a][b];
}
int union_length(vector<int> i1, vector<int> i2) {
return max(i2[1],i1[1])-min(i2[0],i1[0])+1;
}
int length(vector<int> interval) {
return interval[1]-interval[0]+1;
}
bool check(vector<int> i1, vector<int> i2) {
//check whether the length of the union of the intervals is equal to the maximum length of the 2
return max(length(i1),length(i2))==union_length(i1,i2);
}
signed biggest_stadium(signed N, vector<vector<signed>> F) {
//the stadium is valid iff for every pair of cells (a,b) and (c,d),
//everything in the paths (a,b) to (a,d) to (c,d) is inside
//or everything in the paths (a,b) to (a,c) to (c,d) is inside
n=N;
field=F;
pref=vector<vector<int>>(n+1,vector<int>(n+1,0));
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
pref[i+1][j+1] = pref[i+1][j]+pref[i][j+1]-pref[i][j]+F[i][j];
}
}
if (pref[n][n]<=1) {
if (pref[n][n]==0) return n*n;
//subtask 1
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (F[i][j]==1) {
int mi = min({(i+1)*(j+1),(n-i)*(j+1),(i+1)*(n-j),(n-i)*(n-j)});
return n*n-mi;
}
}
}
}
vector<vector<int>> rows(n,{INF,-INF});
vector<vector<int>> cols(n,{INF,-INF});
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (F[i][j]==0) {
rows[i][0] = min(rows[i][0],j);
rows[i][1] = max(rows[i][1],j);
cols[j][0] = min(cols[j][0],i);
cols[j][1] = max(cols[j][1],i);
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (F[i][j]==1) {
if (rows[i][0]<=j && j<=rows[i][1]) {
return 0;
}
if (cols[j][0]<=i && i<=cols[j][1]) {
return 0;
}
}
}
}
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
if (!check(rows[i],rows[j])) {
return 0;
}
}
}
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
if (!check(cols[i],cols[j])) {
return 0;
}
}
}
return n*n-pref[n][n];
}
