#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;
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;
}
