#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;
#define ll long long
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ins insert
#define mp make_pair
const int N = 2009;
map<array<int,4>,int> f;
int n, a[N][N], p[N][N], nxt[N][N];
int calc(int li, int ri, int lj, int rj) {
int l = 1, r = li;
while (l < r) {
int mid = (l + r) >> 1;
if (p[li][rj] - p[li][lj - 1] - p[mid - 1][rj] + p[mid - 1][lj - 1] < 1) r = mid;
else l = mid + 1;
}
if (l < li) return calc(l, ri, lj, rj) + (rj - lj + 1) * (li - l);
l = ri, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (p[mid][rj] - p[mid][lj - 1] - p[ri - 1][rj] + p[ri - 1][lj - 1] < 1) l = mid;
else r = mid - 1;
}
if (l > ri) return calc(li, l, lj, rj) + (rj - lj + 1) * (l - ri);
if (f.count({li, ri, lj, rj})) return f[{li, ri, lj, rj}];
int crr = 0;
if (li > 1) {
for (int j = lj - 1; j < rj; j = nxt[li - 1][j + 1]) {
if (a[li - 1][j + 1]) continue;
int l = j + 1, r = min(rj, nxt[li - 1][j + 1] - 1);
if (l <= r) crr = max(crr, calc(li - 1, ri, l, r) + r - l + 1);
}
}
if (ri < n) {
for (int j = lj - 1; j < rj; j = nxt[ri + 1][j + 1]) {
if (a[ri + 1][j + 1]) continue;
int l = j + 1, r = min(rj, nxt[ri + 1][j + 1] - 1);
if (l <= r) crr = max(crr, calc(li, ri + 1, l, r) + r - l + 1);
}
}
f[{li, ri, lj, rj}] = crr;
return crr;
}
int biggest_stadium(int N, vector<vector<int>> w)
{
n = N;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
a[i][j] = w[i - 1][j - 1];
p[i][j] = p[i][j - 1] + p[i - 1][j] - p[i - 1][j - 1] + a[i][j];
}
}
for(int i=1;i<=n;i++) {
nxt[i][n + 1] = n + 1;
for(int j=n;j>=1;j--) {
if(a[i][j]) nxt[i][j] = j;
else nxt[i][j] = nxt[i][j + 1];
}
}
int res = 0;
for(int i=1;i<=n;i++) {
for(int j=0;j<n;j++) {
if((!j || a[i][j]) && !a[i][j + 1]) {
res = max(res, calc(i, i, j + 1, nxt[i][j + 1] - 1) + nxt[i][j + 1] - j - 1);
}
}
}
return res;
}
