#include "soccer.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e3+5;
int N, ans;
int A[MAXN][MAXN], P[MAXN][MAXN];
map <ll,int> D;
bool exist(int xa,int xb,int ya,int yb) {
return P[xb][yb] - P[xb][ya-1] - P[xa-1][yb] + P[xa-1][ya-1];
}
int enlarge(int x,int ya,int yb);
int solve(int xa,int xb,int ya,int yb) {
ll S = (ll)xa<<33|(ll)xb<<22|(ll)ya<<11|(ll)yb;
if (D.count(S)) return D[S];
int res = 0;
if (xa > 1) {
for (int i=yb;i>=ya;i=A[xa-1][i]-1) {
if (A[xa-1][i] == i) continue;
int j = max(ya,A[xa-1][i]+1);
res = max(res, enlarge(xa,j,i) - (xb-xa+1)*(i-j+1));
}
}
if (xb < N) {
for (int i=yb;i>=ya;i=A[xb+1][i]-1) {
if (A[xb+1][i] == i) continue;
int j = max(ya,A[xb+1][i]+1);
res = max(res, enlarge(xa,j,i) - (xb-xa+1)*(i-j+1));
}
}
return D[S] = res;
}
int enlarge(int x,int ya,int yb) {
int xa=x, xb=x;
int l=1, r=x-1;
while (l<=r) {
int mid = (l+r)/2;
if (exist(mid,x,ya,yb)) {
l = mid+1;
}
else {
xa = mid;
r = mid-1;
}
}
l=x+1, r=N;
while (l<=r) {
int mid = (l+r)/2;
if (exist(x,mid,ya,yb)) {
r = mid-1;
}
else {
xb = mid;
l = mid+1;
}
}
return solve(xa,xb,ya,yb) + (xb-xa+1)*(yb-ya+1);
}
int biggest_stadium(int n, vector<vector<int>> F) {
N = n;
for (int i=1;i<=N;i++) {
for (int j=1;j<=N;j++) {
P[i][j] = P[i-1][j]+P[i][j-1]-P[i-1][j-1]+F[i-1][j-1];
if (F[i-1][j-1]) {
A[i][j] = j;
}
else {
A[i][j] = A[i][j-1];
}
}
}
for (int i=1;i<=N;i++) {
for (int j=N;j>0;j=A[i][j]-1) {
if (A[i][j] == j) continue;
ans = max(ans,enlarge(i,A[i][j]+1,j));
}
}
return ans;
}
