// In the name of Allah
#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define endl '\n'
#define sep ' '
#define pb push_back
#define Mp make_pair
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
const int maxn = 2000 + 4;
int n;
int A[maxn][maxn];
vector<pii> ls;
int val1[maxn][maxn], val2[maxn][maxn];
pii val[maxn]; int dp[maxn][maxn];
bool cmp(pii i, pii j) {
return ((i.S - i.F) > (j.S - j.F));
}
bool is_ok() {
ls.clear();
for (int i = 0; i < n; i++) {
int x = 0;
for (int j = 0; j < n; j++) {
if (A[i][j] != A[i][x]) {
if (A[i][x] == 0) ls.pb(Mp(x, j - 1));
x = j;
}
}
if (A[i][x] == 0) ls.pb(Mp(x, n - 1));
}
sort(all(ls), cmp);
for (int i = 1; i < len(ls); i++) {
if (ls[i].F < ls[i - 1].F || ls[i].S > ls[i - 1].S) return 0;
}
return 1;
}
int check() {
int num = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) num += (A[i][j] == 0);
}
bool ok = 1;
ok &= is_ok();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) swap(A[i][j], A[j][i]);
}
ok &= is_ok();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) swap(A[i][j], A[j][i]);
}
if (ok) return num;
else return 0;
}
int get_val(int x, int y) {
val[x] = Mp(val1[x][y], val2[x][y]);
int lx = x, rx = x;
for (int r = x + 1; r < n; r++) {
if (A[r][y] == 1) break;
val[r] = Mp(val1[r][y], val2[r][y]);
val[r].F = max(val[r].F, val[r - 1].F);
val[r].S = min(val[r].S, val[r - 1].S);
rx = r;
}
for (int r = x - 1; r >= 0; r--) {
if (A[r][y] == 1) break;
val[r] = Mp(val1[r][y], val2[r][y]);
val[r].F = max(val[r].F, val[r + 1].F);
val[r].S = min(val[r].S, val[r + 1].S);
lx = r;
}
for (int i = x; i >= lx; i--) {
for (int j = x; j <= rx; j++) {
int valx = min(val[i].S, val[j].S) - max(val[i].F, val[j].F) + 1;
if (i == x && j == x) {
dp[i][j] = valx;
}
else {
dp[i][j] = 0;
if (i + 1 <= x) {
dp[i][j] = max(dp[i][j], dp[i + 1][j] + valx);
}
if (j - 1 >= x) {
dp[i][j] = max(dp[i][j], dp[i][j - 1] + valx);
}
}
}
}
return dp[lx][rx];
}
int solve() {
int mx = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (A[i][j] == 1) continue;
mx = max(mx, get_val(i, j));
}
}
return mx;
}
int biggest_stadium(int N, vector<vector<int>> F) {
n = N;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
A[i][j] = F[i][j];
if (A[i][j] == 1) ls.pb(Mp(i, j));
}
}
if (len(ls) == 0) return (n * n);
else if (len(ls) == 1) {
int i = ls.back().F, j = ls.back().S;
return (n * n) - (min(i + 1, n - i) * min(j + 1, n - j));
}
for (int i = 0; i < n; i++) {
int x = 0;
for (int j = 0; j < n; j++) {
if (A[i][j] != A[i][x]) x = j;
val1[i][j] = x;
}
x = n - 1;
for (int j = n - 1; j >= 0; j--) {
if (A[i][j] != A[i][x]) x = j;
val2[i][j] = x;
}
}
if (n <= 30) return solve();
else return check();
}
